#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <bitset>
#include <utility>

using namespace std;

#define DIM 50005
#define INF 2e10

vector <vector <pair <int, int> > > V;
priority_queue <pair <int, int> > MyQue;
bitset <DIM> MyBitset;
long long d[DIM];
int N, M, x, y, cost;

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

    fscanf(fin, "%d %d\n", &N, &M);

    V.resize(N + 2);

    for(int i = 1; i <= M; ++i) {
        fscanf(fin, "%d %d %d\n", &x, &y, &cost);

        V[x].push_back(make_pair(y, cost));
    }

    MyQue.push(make_pair(0, 1));

    for(int i = 2; i <= N; ++i) {
        d[i] = INF;
    }

    while(!MyQue.empty()) {
        int x = MyQue.top().second;
        MyQue.pop();

        while(!MyQue.empty() && MyBitset[x] == 1) {
            x = MyQue.top().second;
            MyQue.pop();
        }

        MyBitset[x] = 1;

        for(unsigned int i = 0; i < V[x].size(); ++i) {
            if(1LL * V[x][i].second + d[x] < d[V[x][i].first]) {
                d[V[x][i].first] = 1LL * V[x][i].second + d[x];
                MyQue.push(make_pair(-d[V[x][i].first], V[x][i].first));
            }
        }
    }

    for(int i = 2; i <= N; ++i) {
        fprintf(fout, "%lld ", (d[i] == INF ? 0 : d[i]));
    }

    fprintf(fout, "\n");

    return 0;
}