#include <bits/stdc++.h>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct cue
{
    int x, cost;
    bool operator< ( cue other ) const
    {
        return  cost > other.cost;
    };
};

long long c[50001];
vector <cue> a[50001];
priority_queue <cue> pq;

void precalc()
{
    for ( int i = 1; i <= 50000; i ++ )
        c[i] = LLONG_MAX;
}

int main()
{
    int n, m;
    f >> n >> m;
    precalc();
    for ( int i = 1; i <= m; i ++ )
    {
        int x, y, c;
        f >> x >> y >> c;
        a[x].push_back( { y, c } );
    }
    pq.push({ 1, 0 });
    c[1] = 0;
    while ( pq.size() )
    {
        cue current = pq.top();
        pq.pop();
        if ( current.cost == c[current.x] )
        {
            for ( int i = 0; i < a[current.x].size(); i ++ )
            {
                if ( c[a[current.x][i].x] > current.cost + a[current.x][i].cost )
                {
                    c[ a[current.x][i].x ] = current.cost + a[current.x][i].cost;
                    pq.push( { a[current.x][i].x, c[ a[current.x][i].x ] } );
                }
            }
        }
    }
    for ( int i = 2; i <= n; i ++ )
    {
        if ( c[i] == LLONG_MAX )
            c[i] = 0;
        g << c[i] << " ";
    }
    return 0;
}