#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;

    //sure[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 )
    {
//cout << "Wat";
//cout<< qu.top().nod << " " << qu.top().val << "\n";
        while( qu.size() && ( dist[qu.top().nod] != qu.top().val || sure[qu.top().nod] ) )
        {
            qu.pop();
        }

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

        //cout << hnods.nod << ": \n";
        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 );
                //cout << "   " <<  nnods.nod << " " << nnods.val << "\n";
            }
        }
    }

    for( int i = 2; i <= N; ++i )
    {
        //cout << i << ": " << dist[i] - 1 << "\n";
        fout << max( dist[i] - 1, 0 ) << " ";
    }


    return 0;
}