#include <cstdio>
#include <queue>
using namespace std;
#define NMAX 50005
#define INF 2000005
typedef pair<int, int> ii;

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

void Dij() {

    int i;
    priority_queue<ii, vector<ii>, greater<ii> > pq;
    int child, parent, cost, dist;

    pq.push(ii(0,1));

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

        if(d[parent] < dist)
            continue;

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

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

int main() {

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

    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=2; i<=n; i++)
        d[i] = INF;

    Dij();

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

    return 0;
}