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

using namespace std;

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

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 Dial(vector<PER> G[], int N, int D[], int P[])
{
    for ( int i = 0; i <= N; ++i )
        D[i] = inf, P[i] = 0;
    D[1] = 0;

    queue<int> Q[maxc + 1];
    Q[0].push(1);

    int cnt = 1;
    for ( int cst = 0; cnt; ++cst )
        for ( ; !Q[cst].empty(); Q[cst].pop() )
        {
            int j = Q[cst].front();
            --cnt;

            if ( D[j] != cst )
                continue;

            vector<PER>::iterator i;
            for ( i = G[j].begin(); i != G[j].end(); ++i )
                if ( D[j] + i->second < D[ i->first ] )
                {
                    D[ i->first ] = D[j] + i->second;
                    P[ i->first ] = j;

                    Q[ D[ i->first ] & maxc ].push( i->first ); // modulo (maxc + 1)
                    ++cnt;
                }
        }
}

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

    Dial(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;
}