#include <queue>
#include <cstdio>
#define INF (1<<21)
#define source 1
#define NMAX 50005
#define MMAX 500001

using namespace std;

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

int N, M;
int U[NMAX];
int D[NMAX];

vector<pair<int, int> > G[NMAX];
vector<pair<int, int> >::iterator it;
queue<int> Q;

void ReadData() {
    int u, v, cost;
    fscanf(fin, "%d %d", &N, &M);
    for(int i = 1; i <= M; ++ i) {
        fscanf(fin, "%d %d %d", &u, &v, &cost);
        G[u].push_back(make_pair(v, cost));
    }
}

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

void BellmanFord() {
    Init();
    Q.push(source);
    while(!Q.empty()) {
        int nod = Q.front();
        Q.pop();
        for(it = G[nod].begin(); it != G[nod].end(); ++ it)
            if(D[it->first] > D[nod] + it->second) {
                D[it->first] = D[nod] + it->second;
                ++ U[it->first];
                Q.push(it->first);
            }
    }
}

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

int main() {
    ReadData();
    BellmanFord();
    ShowData();
    return 0;
}