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

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

void Daijtra(int nod){
    priority_queue<ii, vector<ii>, greater<ii> > pq;
    int i, dist, cost, child;
    pq.push(ii(0, nod));
    d[nod] = 0;

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

        if(d[nod] < dist)
            continue;

        for(i=0; i<a[nod].size(); i++){
            child = a[nod][i].first;
            cost = a[nod][i].second;

            if(d[child] > dist + cost){
                d[child] = dist + cost;
                pq.push(ii(d[child], child));
            }
        }
    }
}

int main(){

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

    start = 1;
    fscanf(fin, "%d %d", &n, &m);
    for(i=1; i<=m; i++){
        fscanf(fin, "%d %d %d", &x, &y, &z);
        a[x].push_back(ii(y, z));
    }

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

    Daijtra(start);

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