#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> ii;
#define NMAX 50005
#define INF 1000000005
vector<ii> a[NMAX];
int n, m, d[NMAX];

void Dij() {
    int child, dist, cost, node;

    priority_queue<ii, vector<ii>, greater<ii> >pq;
    pq.push(ii(0, 1));
    d[1] = 0;

    while(!pq.empty()) {

        node = pq.top().second;
        dist = pq.top().first;
        pq.pop();

        if(dist > d[node])
            continue;

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

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

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

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

    for(int i=2; i<=n; i++)
        d[i] = INF;
    d[1] = 0;

    Dij();

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