#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#define NMAX 50002
#define INF 1000000005
using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int n,m;
vector< pair<int,int> > a[NMAX];
priority_queue<pair<int,int> > heap;
pair<int,int> node;
int d[NMAX],x,y,c;

int main()
{
    in >> n >> m;
    for(int i=0;i<m;i++) {
        in >> x >> y >> c;
        a[x].push_back(make_pair(c,y));
        //a[y].push_back(make_pair(c,x));
    }

    for(int i=1;i<=n;i++) {
        d[i] = INF;
    }
    d[1]=0;
    heap.push(make_pair(d[1],1));

    while(!heap.empty()) {
        node = heap.top(); heap.pop();
        //cout << node.first << " " << node.second << endl;
        for(int i=0;i<a[node.second].size();i++) {
            if(d[a[node.second][i].second] > node.first + a[node.second][i].first){
                d[a[node.second][i].second] = node.first + a[node.second][i].first;
                heap.push(make_pair(d[a[node.second][i].second],a[node.second][i].second ));
            }
        }
    }

    for(int i=2;i<=n;i++) {
        if(d[i] ==INF) out << 0 << " ";
        else out << d[i] << " ";
    }
    return 0;
}