#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define pb push_back
#define ll long long

using namespace std;

 ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int NLIM = 50000 + 10;

struct nodS
{
    int nod;
    ll val;
};


int N, M;
vector< int > graph[NLIM];
vector< ll > cost[NLIM];

int sure[NLIM];
int dist[NLIM];

class comparC
{
public:
    bool operator() ( nodS nod1, nodS nod2 )
    {
        return nod1.val > nod2.val;
    }
};


int main()
{
    fin >> N >> M;
    for( int i = 0; i < M; ++i )
    {
        int x, y, c;
        fin >> x >> y >> c;
        graph[x].pb( y );
        //graph[y].pb( x );
        cost[x].pb( c );
        //cost[y].pb( c );
    }

    int ST = 1;

    dist[ST] = 1;

    priority_queue< nodS, vector< nodS >, comparC > qu;
    nodS STnod = { ST, dist[ST] };
    qu.push( STnod );

    int snr = 1;
   // while( snr < N )
    for( int snr = 1; snr < N; ++snr )
    {
        while( qu.size() && ( dist[qu.top().nod] != qu.top().val || sure[qu.top().nod] ) )
            qu.pop();

        if( !qu.size() )
            break;
        nodS hnods = qu.top();
        qu.pop();
        sure[hnods.nod] = 1; ++snr;

        for( int j = 0; j < graph[hnods.nod].size(); ++j )
        {
            int nnod = graph[hnods.nod][j];
            int hcost = cost[hnods.nod][j];
            if( dist[nnod] == 0 || dist[hnods.nod] + hcost < dist[nnod] )
            {
                dist[nnod] = dist[hnods.nod] + hcost;

                nodS nnods = { nnod, dist[nnod] };
                qu.push( nnods );
            }
        }
    }

    for( int i = 2; i <= N; ++i )
        fout << max( dist[i] - 1, 0 ) << " ";

    return 0;
}