#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
#define NMAX 50005
#define INFINIT 1000000000

int n, m, d[NMAX], start = 1;
typedef pair<int, int> ii;
vector<ii> a[NMAX];

void Daijtra(int nod){
    priority_queue<ii, vector<ii>, greater<ii> >pq;
    pq.push(ii(0, start));

    int dist = 0, current = start, i;

    while(!pq.empty()){
        dist = pq.top().first;
        current = pq.top().second;

        pq.pop();

        if(dist > d[current])
            continue;

        for(i=0; i<(int) a[current].size(); i++){
            if( d[ a[current][i].first ] > dist + a[current][i].second ){
                d[ a[current][i].first ] = dist + a[current][i].second;
                pq.push(ii(d[ a[current][i].first ], a[current][i].first));
            }
        }

        //pq.pop();
    }

}

int main(){

    int x, y, c;
    FILE *fin, *fout;
    fin = fopen("dijkstra.in", "r");
    fout = fopen("dijkstra.out", "w");

    fscanf(fin, "%d%d", &n, &m);
    while(fscanf(fin, "%d%d%d", &x, &y, &c) != EOF){
        a[x].push_back(ii(y, c));
    }

    for(int i=1; i<=n ; i++){
        d[i] = INFINIT;
    }

    Daijtra(start);

    for(int i=2; i<=n; i++){
        if(d[i] == INFINIT)
            fprintf(fout, "0 ");
        else
            fprintf(fout, "%d ", d[i]);
    }

    return 0;
}