#include<bits/stdc++.h>
using namespace std;
long long n,m,s,a[300][300],b[2000000];
bool k[200000];
void di(){
	memset(b,0x3f,sizeof(b));
	memset(k,0,sizeof(k));
	b[1]=0;
	for(int i=1;i<n;i++){int p=0;
		for(int j=1;j<=n;j++){
			if(!k[j]&&(p==0||b[j]<b[p]))p=j;
			k[p]=1;
			for(int x=1;x<=n;x++){
				b[x]=min(b[x],b[p]+a[p][x]);
			}
		}
	}
}

int main(){
	long long q,w,e;
	cin>>n>>m>>s;
	memset(a,0x3f,sizeof(a));
	for(int i=1;i<=n;i++)a[i][i]=0;
		for(int i=1;i<=m;i++){
			cin>>q>>w>>e;
			a[q][w]=min(a[q][w],e);
			
		
	}
	di();
	for(int i=1;i<=n;i++)cout<<b[i]<<' ';
	return 0;
}```