#include <cstdio>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
#define IN "dijkstra.in"
#define OUT "dijkstra.out"
#define l 50003
#define pb push_back
int d[l],sol[l];
bool fr[l];
vector<int>G[l];
vector<int>C[l];
queue<int>Q;
int k , n , m;
void Read()
{
int i , v , x , y;
scanf ( "%d%d" , &n , &m );
for ( i = 1 ; i <= m ; i ++ ){
scanf ( "%d%d%d" , &x , &y , &v );
G[x].pb(y),C[x].pb(v);
}
}
void Init()
{
int i;
for ( i = 2 ; i <= l ; i ++ )
d[i] = INT_MAX;
}
void Precalc()
{
int i , x;
sol[k=1] = 1;
for ( i = 0 ; i < G[1].size() ; i ++ )
Q.push(G[1][i]) , sol[++k] = G[1][i];
while ( !Q.empty() )
{
x = Q.front();
Q.pop();
for ( i = 0 ; i < G[x].size() ; i ++ )
if ( fr[G[x][i]] == 0 )
sol[++k] = G[x][i] , Q.push(G[x][i]) , fr[G[x][i]] = 1;
// Q.pop();
}
}
void Solve()
{
Init();
int i , j , z;
for ( i = 1 ; i <= k ; i ++ ){
for ( j = 0 ; j < G[sol[i]].size() ; j ++ )
{
if ( d[sol[i]]+C[sol[i]][j] < d[G[sol[i]][j]] )
d[G[sol[i]]
[j]] = d[sol[i]]+C[sol[i]][j];
}
}
for ( i = 2 ; i <= n ; i ++ )
printf ( "%d " , d[i] );
}
int main()
{
freopen ( IN , "r" , stdin );
freopen ( OUT , "w" , stdout );
Read();
Precalc();
Solve();
}