#include <fstream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

const int maxn = 50002;
const int inf = 1 << 29;

typedef pair<int, int> PER;

void citire(vector<PER> G[], int &N, int &M)
{
    ifstream in("dijkstra.in");
    in >> N >> M;

    int x, y, c;
    for ( int i = 1; i <= M; ++i )
    {
        in >> x >> y >> c;
        G[x].push_back( make_pair(y, c) );
       // G[y].push_back( make_pair(x, c) );
    }

    in.close();
}

void dijkstra(vector<PER> G[], int N, int D[], int P[])
{
    for ( int i = 1; i <= N; ++i )
        D[i] = inf, P[i] = 0;
    D[1] = 0;

    priority_queue<PER, vector<PER>, greater<PER> > Q;

    Q.push( make_pair(D[1], 1) );
    while ( !Q.empty() )
    {
        PER tmp = Q.top();
        Q.pop();

        int nod = tmp.second;

        for ( int i = 0; i < G[nod].size(); ++i )
            if ( D[nod] + G[nod][i].second < D[ G[nod][i].first ] )
            {
                D[ G[nod][i].first ] = D[nod] + G[nod][i].second;
                P[ G[nod][i].first ] = nod;

                Q.push( make_pair(D[ G[nod][i].first ], G[nod][i].first) );
            }
    }
}

int main()
{
    int N, M, D[maxn], P[maxn];
    vector<PER> G[maxn];
    citire(G, N, M);

    dijkstra(G, N, D, P);
    ofstream out("dijkstra.out");

    for ( int i = 2; i <= N; ++i )
        if ( D[i] == inf )
            out << 0 << ' ';
        else
            out << D[i] << ' ';

    out.close();
    return 0;
}