#include<iostream>

#include<cstdio>

#include<utility>

#include<queue>

#include<cstring>

using namespace std;

#define INF 1000000000

int d[20005];

int n,m,a,b,c;

int u[200005];

int v[200005];

int l[200005];

int nxt[200005]; // next[e] 记录e的下一条边的标号

int first[20005]; // first[u] 是u的"第一条" 边的编号

int vis[20005];

int min(int a,int b){

return a<b?a:b;

}

int main(){

cin>>n>>m;

for(int i=0;i<=n;i++)

first[i]=-1;

for(int i=1;i<=m;i++){

scanf("%d%d%d",&u[i],&v[i],&l[i]);

nxt[i]=first[u[i]];

first[u[i]]=i;

}

for(int i=1;i<=n;i++)

d[i]=(i==1?0:INF);

memset(vis, 0, sizeof(vis));

queue<int> q;

q.push(1);

while(!q.empty()){

int x=q.front();

q.pop();

vis[x]=0;

for(int e=first[x];e!=-1;e=nxt[e]){

if(d[v[e]]>d[x]+l[e]){

d[v[e]]=d[x]+l[e];

if(!vis[v[e]]){

vis[v[e]]=1;

q.push(v[e]);

}

}

}

}

for(int i=1;i<=n;i++)

cout<<d[i]<<endl;

return 0;

}

5 7

1 2 2

1 5 10

2 3 3

2 5 7

3 4 4

4 5 5

5 3 6