#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] = -1;
}

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 x = pq.top();
        pq.pop();
        for ( int i = 0; i < a[x.x].size(); i ++ )
        {
            if ( c[ a[x.x][i].x ] == -1 )
            {
                c[ a[x.x][i].x ] = x.cost + a[x.x][i].cost;
                pq.push( { a[x.x][i].x, c[ a[x.x][i].x ] } );
            }
        }
    }
    for ( int i = 2; i <= n; i ++ )
        g << c[i] << " ";
    return 0;
}