using ull = unsigned long long;
ull qpow(ull a, ull b, ull mod) {
	ull res = 1;
	for (a %= mod; b; b >>= 1) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
	}
	return res;
}

int gcd(int a, int b) {
	while (b != 0) {
    	int tmp = a;
    	a = b;
    	b = tmp % b;
    }
    return a;
}

bool isPrime(int a) {
    if (a < 2) return 0;
    for (int i = 2; (long long)i * i <= a; ++i)  // 防溢出
    if (a % i == 0) return 0;
    return 1;
}

// 埃氏筛
vector<int> prime;
bool is_prime[N];
void Eratosthenes(int n) {
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i <= n; ++i) is_prime[i] = true;
  for (int i = 2; i * i <= n; ++i) {
    if (is_prime[i])
      for (int j = i * i; j <= n; j += i) is_prime[j] = false;
  }
  for (int i = 2; i <= n; ++i)
    if (is_prime[i]) prime.push_back(i);
}

// 递归实现斐波那契数列（时间复杂度 O(2^n)）
int fib_recursive(int n) {
    if (n <= 1) return n;
    return fib_recursive(n-1) + fib_recursive(n-2);
}

// 迭代实现斐波那契数列（时间复杂度 O(n)）
int fib_iterative(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

/*配合记忆化数组后*/

// 自顶向下（递归+记忆化）
int memo[1000] = {0};
int fib_top_down(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib_top_down(n-1) + fib_top_down(n-2);
    return memo[n];
}

// 自底向上（迭代动态规划）
int fib_bottom_up(int n) {
    int dp[n+1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

struct road{ int to;  int w; };
struct node{ vector<road> r; };

int dis[100005];
int vis[100005];
node arr[100003];

void solve(){
    int n,m,s;
    cin>>n>>m>>s;
    int t1,t2,tw, temp, tx;  s=1;
    for(int i=0;i<m;i++){
        cin>>t1>>t2>>tw;
        arr[t1].r.push_back({t2,tw});
        // arr[t2].r.push_back({t1,tw}); //有向边就注释，无向边就留下
    }
    fill(dis,dis+n+1,INT_MAX);
    fill(vis,vis+n+1,0);
    dis[1]=0;
    priority_queue< 
        pair<int,int>, 
        vector<pair<int,int>>, 
        greater<pair<int,int>> 
    > pq;
    pq.push({0,1});
    
    while(!pq.empty()){
        auto[d, i] = pq.top();  pq.pop();
        if(vis[i]) continue;
        vis[i] = 1;

        for(auto iter:arr[i].r){
            temp = dis[i]+ iter.w;
            tx = iter.to;
            if(temp<dis[tx]){
                dis[tx] = temp;
                pq.push({dis[tx],tx});
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<" ";
    }
}

// 加法 版本
int arr[100005];

struct node{
    int l,r;
    int sum=0,lz=0;
} tree[400005];

void build(int l, int r, int i=1){
    tree[i].l = l; tree[i].r = r;
    if(r==l){
        tree[i].sum = arr[l]; return;
    }
    int mid = (l+r)>>1;
    build(l,mid,2*i);
    build(mid+1,r,2*i+1);
    tree[i].sum = tree[2*i].sum + tree[2*i+1].sum;
}

void pushdown(int i){
    if(tree[i].l == tree[i].r) return;
    if(tree[i].lz!=0){
        int lz = tree[i].lz;
        tree[2*i].lz += lz; 
        tree[2*i+1].lz += lz;
        tree[2*i].sum += lz*(tree[2*i].r-tree[2*i].l+1);
        tree[2*i+1].sum += lz*(tree[2*i+1].r-tree[2*i+1].l+1);
        tree[i].lz = 0;
    }
}

// 乘法+加法 版本
int arr[100005]; int m;
struct node{
    int l,r;
    int sum;
    int plz=0,mlz=1;
} tree[400005];

void build(int l, int r, int i=1){
    tree[i].l = l; tree[i].r = r;
    if(l==r){
        tree[i].sum = arr[l];
        return;
    }
    int mid = (l+r)>>1;
    build(l,mid,i<<1);
    build(mid+1,r,i<<1|1);
    tree[i].sum = (tree[i<<1].sum + tree[i<<1|1].sum)%m;
}

void pushdown(int i){
    if(tree[i].l==tree[i].r) return;
    if(tree[i].plz!=0 || tree[i].mlz!=1){
        int plz = tree[i].plz, mlz = tree[i].mlz;
        tree[i<<1].mlz = (tree[i<<1].mlz*mlz)%m;
        tree[i<<1].plz = (tree[i<<1].plz*mlz+plz)%m;
        tree[i<<1|1].mlz = (tree[i<<1|1].mlz*mlz)%m;
        tree[i<<1|1].plz = (tree[i<<1|1].plz*mlz+plz)%m;

        int s1=tree[i<<1].r-tree[i<<1].l+1, s2=tree[i<<1|1].r-tree[i<<1|1].l+1;
        tree[i<<1].sum = (mlz*tree[i<<1].sum+plz*s1)%m;
        tree[i<<1|1].sum = (mlz*tree[i<<1|1].sum+plz*s2)%m;

        tree[i].plz = 0; tree[i].mlz = 1;
    }
}

void add(int l, int r, int mk, int pk, int i=1){
    if(tree[i].l>=l && tree[i].r<=r){
        int s = tree[i].r - tree[i].l +1;
        tree[i].mlz = (tree[i].mlz*mk)%m;
        tree[i].plz = (mk*tree[i].plz + pk)%m;
        tree[i].sum = (mk*tree[i].sum+pk*s)%m;
        return;
    }
    if(tree[i].l>r || tree[i].r<l) return;
    pushdown(i);
    if(tree[i<<1].r>=l) add(l,r,mk,pk,i<<1);
    if(tree[i<<1|1].l<=r) add(l,r,mk,pk,i<<1|1);
    tree[i].sum = (tree[i<<1].sum + tree[i<<1|1].sum)%m;
}

int search(int l, int r, int i=1){
    if(tree[i].l>=l && tree[i].r<=r) return tree[i].sum;
    if(tree[i].l>r || tree[i].r<l) return 0;
    pushdown(i);
    int s = 0;
    if(tree[i<<1].r>=l) s = (s+search(l,r,i<<1))%m;
    if(tree[i<<1|1].l<=r) s = (s+search(l,r,i<<1|1))%m;
    return s;
}

int pre[200005];

void build(int n){
    for(int i=0;i<=n;i++) pre[i]=i;
}
int find(int i){
    if(pre[i] == i) return i;
    return pre[i] = find(pre[i]);
}
void join(int i, int j){
    int x = find(i), y = find(j);
    pre[x] = y;
}
bool isSet(int i, int j){ 
    return find(i)==find(j);
}

void kmp(string s, string t){
	int n=s.length(), l=t.length();
	vector<int> next(l,0);
	vector<int> ans;
	int i=1,pre=0,p=0;
	while(i<l){
		if(t[i]==t[pre]){
			next[i] = (++pre); i++;
		}
		else{
			if(pre==0) i++;
			else pre = next[pre-1];
		}
	}
	i=0;
	while(i<n){
		if(s[i]==t[p]){
			i++; p++;
		}
		else if(p==0) i++;
		else p = next[p-1];

		if(p==l){
			ans.push_back(i-p+1);
			p = next[p-1];
		}
	}
	
	for(int it:ans) cout<<it<<endl;
	//for(int i=0;i<l;i++) cout<<next[i]<<" ";
	//cout<<endl;
}

//  codeforce
#include<bits/stdc++.h>
using namespace std;
#define ll long long

void solve(){
    
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

//  AtCoder
#include<bits/stdc++.h>
using namespace std;
#define ll long long

void solve(){
    
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

struct node {
    int a;
    double b;

    // 重载等于操作符
    bool operator==(const node& other) const {
        return a == other.a && b == other.b;
    }

    // 重载小于操作符，用于排序和 std::map
    bool operator<(const node& other) const {
        if (a != other.a) return a < other.a;
        return b < other.b;
    }
};

// 为 node 定义哈希函数
struct node_hash {
    size_t operator()(const node& s) const {
        return hash<int>()(s.a) ^ hash<double>()(s.b);
    }
};

template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar_unlocked();
	for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
	for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}