#include <iostream>
#include <cstring>
#include <fstream>
#include <vector>
using namespace std;
 
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
 
#define INF 0x3f3f3f3f
#define NMAX 50004
 
int a, b, c, N, M;
int p, q;
int k;
 
struct nod {
    int vf , c;
    nod(){};
    nod(int _vf,int _c){vf = _vf; c = _c;};
};
 
vector<nod> v[NMAX];
int d[NMAX];
int in[NMAX];
 
int main() {
    fin >> N >> M;
    for (int i = 0; i < M; ++i) {
        fin >> a >> b >> c;
        v[b].push_back(nod(a,c));
    }
    for (int i = 2; i <= N; ++i) d[i] = INF;
    do {
        k = 0;
        for (int i = 2; i <= N; ++i) {
            for (vector<nod> :: iterator it = v[i].begin(); it != v[i].end(); ++it) {
                if (d[it->vf] + (it->c) < d[i]) {
                    d[i] = d[it->vf] + it->c;
                    k = 1;
                }
            }
        }
    }while(!k);
    for (int i = 2; i <= N; ++i) 
        fout << d[i] << ' ';
    fout << '\n';
    return 0;
}