#include <cstdio>
#include <limits.h>
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;
#define INF 30001 //numarul de noduri ?
typedef pair<int, int> PII;

int main()
{
    ifstream fin("dijkstra.in");
    int N,M;
    fin>>N>>M;
    vector< vector<PII> > edges(N);
    for(int i = 0; i<M ;i++) {
        int v1,v2,cost;
        fin>>v1>>v2>>cost;
        edges[v1-1].push_back(make_pair(cost,v2-1));
    }

    int s = 0;
    vector<int> dist(N,INF);

    priority_queue< PII, vector<PII>, greater<PII> > Q;
    dist[s] = 0;
    Q.push(make_pair(0,s));
    int k = 0;
    while(!Q.empty() && k <= N) {
        PII p = Q.top();
        Q.pop();
        int node = p.second;
        if(p.first != dist[node]) continue;

        for(vector<PII>::iterator it = edges[node].begin(); it!= edges[node].end() ;++it) {

            if(dist[it->second] > dist[node] + it->first) {
                dist[it->second] = dist[node] + it->first;
                Q.push(make_pair(dist[it->second],it->second));
            }
        }
        k++;
    }
    fin.close();
    ofstream fout("dijkstra.out");
    for(int i = 1;i < N;i++)
    {
        fout<<(dist[i] == INF ? 0 : dist[i] )<<( i == N-1 ? '\n':' ');
    }

    return 0;
}