#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
#define inf 2000000000
vector < pair<int,int> > A[50001];
vector < pair<int,int> > :: iterator it;
int N, D[50001], V[50001], NH;
struct heap{
    int c;
    int nod;
}H[50002];
void add(int cost, int nod){
    int p,c;
    NH++;
    H[NH].nod = nod;
    H[NH].c = cost;
    c = NH;
    p = c / 2;
    while( p > 0 && H[p].c > H[c].c ){
        swap(H[p], H[c]);
        c = p;
        p = c / 2;
    }
}

void del(){
    int d, c;
    c = 1;
    swap(H[1],H[NH]);
    NH--;
    while(1){
        d = 2 * c;
        if(d > NH)
            break;
        if( d + 1 <= NH && H[d+1].c < H[d].c )
            d++;
        if( H[c].c > H[d].c ){
            swap(H[c],H[d]);
            c = d;
        }
        else
            break;
    }

}

int main()
{
    int m, i, x, y, c, k, ok, min;
    f >> N >> m;
    for(i = 1; i <= m; i++){
        f >> x >> y >> c;
        A[x].push_back(make_pair(y,c));
    }
    for( i = 1; i <= N; i++ ){
        D[i] = inf;
    }
    D[1] = 0;
    ok = 1;
    add(0,1);
    add(inf,-1);
    while(ok == 1){
        min = H[1].c;
        k = H[1].nod;
        del();
        if(min != inf){
            V[k] = 1;
            for( it = A[k].begin(); it < A[k].end(); it++ )
                if( D[it->first] > D[k] + it->second ){
                    D[it->first] = D[k] + it->second;
                    if( V[it->first] == 0)
                        add(D[it->first],it->first);
                }
        }
        else
            ok = 0;
    }
    for(i = 2; i <= N; i++)
        if(D[i] == inf)
            g << "0 ";
        else
            g << D[i] << " ";
    return 0;
}