#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50005
#define INF 100000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct pereche{
    int x, c;
};

int n, m, nod1, nod2, cost;
int dist[NMAX];
vector<pair<int, int> > G[NMAX];
priority_queue<pair<int, int> > h;

int main(){
    int i, nod, cost; pereche aux;
    fin>>n>>m;
    for(i = 0; i < m; i++){
        fin >> nod1 >> nod2 >> cost;
        G[nod1].push_back(make_pair(nod2, cost));
    }
    for(i = 2; i <= n; i++) dist[i] = INF;
    dist[1] = 0;
    h.push(make_pair(1, 0));
    while (!h.empty()){
        nod = h.top().first;
        cost = h.top().second;
        h.pop();
        for (vector<pair<int, int> >::iterator it = G[nod].begin(); it != G[nod].end(); it++){
            nod2 = it -> first;
            cost = it -> second;
            if(dist[nod2] > dist[nod] + cost){
                dist[nod2] = dist[nod] + cost;
                h.push(make_pair(nod2, dist[nod2]));
            }
        }
    }
    for (int i = 2; i <= n; ++i) {
        if (dist[i] == INF) {
            dist[i] = 0;
        }
        fout << dist[i] << ' ';
    }
    fout << '\n';
    fout.close();
}