#include <stdio.h>
#include <set>
#include <vector>

using namespace std;

#define inf 1000000000

long n, i, j, k, d[50010], a, b, co, m, nod, cost;
vector <long> v[50010], c[50010];
set < pair <long, long> > g;

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(i = 1; i <= m ; i++)
    { 
        scanf("%d %d %d", &a, &b, &co);
        v[a].push_back(b);
        c[a].push_back(co);
    }
    for(i = 2; i <= n; i++)
    d[i]=inf;
    g.insert( make_pair(0, 1) );
    while (g.size() > 0)
    {
        cost=(*g.begin()).first;
        nod=(*g.begin()).second;
        g.erase( *g.begin() );
        for(i=0; i<v[nod].size(); i++)
        if(d[ v[ nod ][ i ] ] > cost + c[ nod ][ i ])
        {
            d[ v[ nod ][ i ] ] = cost + c[ nod ] [ i ];
            g.insert( make_pair( d[ v[ nod ][ i ] ], v[ nod ][ i ]));
        }
    }
    i=0;
    for(i=2; i<=n; i++)
    if( d[i] == inf )
    {
        printf("%d ", 0);
    }
    else
    {
        printf("%d ", d[i]);
    }
    return 0;
}