#include<cstdio>
#include<queue>
#include<vector>

using namespace std;

int n, m, best[50009];

priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > heapp;
vector < pair < int , int > > edge[50009];

int main()
{
freopen ("dijkstra.in", "r", stdin);
freopen ("dijkstra.out", "w", stdout);

scanf ("%d%d", &n, &m);
while (m)
{
    int a, b, c;
    m --;
    scanf ("%d %d %d", &a, &b, &c);
    edge [ a ] . push_back ( make_pair ( b , c ) ) ;
}

for (int i=1; i<=n; i++)
    best[i] = 1<<30;
heapp . push ( make_pair (0, 1) ) ;
while (!heapp . empty () )
{
    pair < int , int > X = heapp . top();
    heapp . pop();
    if ( best [ X . second ] != (1<<30) )
        continue ;
    best [ X . second ] = X . first;
    for (vector < pair < int , int > > :: iterator it = edge[X.second].begin(); it != edge[X.second].end(); it++)
            heapp . push ( make_pair (best[X.second] + it->second, it->first));
}

for (int i=2; i<=n; i++)
    if (best[i] == ( 1 << 30 ) ) printf ("0 ");
    else printf ("%d ", best[i]);
printf ("\n");

return 0;
}