#include<fstream>

#include<queue>

#include<vector>

#include<bitset>

#include<cstring>

using namespace std;

 

const int Max_N = 50100;

const int INF = 0x3f3f3f3f;

 

//const char in[] = "dijkstra.in";

//const char out[]= "dijkstra.out";

 

ifstream f("dijkstra.in");

ofstream g("dijkstra.out");

 

#define pb push_back

 

vector<pair<int, int> >G[Max_N];

queue<int>Q;

 

int dist[Max_N], N, M;

bool in_Q[Max_N];

 

int main()

{

//freopen(in,"r",stdin);

//freopen(out,"w",stdout);

//scanf("%d %d", &N, &M);

f>>N>>M;

memset(dist, INF, sizeof(dist));

int a, b, cost, x;

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

//scanf("%d%d%d", &a, &b, &cost), 

{

f>>a>>b>>cost;

G[a].pb(make_pair(b, cost));

}



dist[1] = 0, Q.push(1), in_Q[1] = true;

 

while( Q.size() )

{

x = Q.front();

Q.pop();

in_Q[x] = false;
for (vector< pair<int, int> >::iterator it = G[x].begin(); it != G[x].end(); ++it)

{

if(dist[it->first] > dist[x] + it->second)

{

dist[it->first] = dist[x] + it->second;

if(!in_Q[it->first])

{

Q.push(it->first);

in_Q[it->first] = true;

}

}

}

}

for(int i = 2 ;  i <= N ; ++i)

//printf("%d ", dist[i] == INF ? 0 : dist[i]);

g << (dist[i] == INF ? 0 : dist[i]) << ' ';

return 0;

}