#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;

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

const int Nmax = 50010;
const long long Valmax = 10000000000;
typedef pair<long long, int> value_pair;

class Compare{
public:
    bool operator()(value_pair a, value_pair b){
        return a.first > b.first;
    }
};

int N,M,a,b,c;
vector<pair<int,int> > v[Nmax];
long long dist[Nmax];
priority_queue<value_pair, vector<value_pair>, Compare> q;


int main()
{
    f>>N>>M;
    for(;M;M--){
        f>>a>>b>>c;
        v[a].push_back({b, c});
    }
    memset(dist, 127, sizeof(dist));
    dist[1] = 0;
    q.push({0, 1});
    while(q.size()){
        auto top = q.top();
        q.pop();
        long long curr_dist = top.first;
        int node = top.second;
        //cout<<node<<' '<<curr_dist<<'\n';
        if(dist[node] != curr_dist)
            continue;
        for(auto it:v[node])
            if(dist[it.first] > dist[node] + it.second){
                dist[it.first] = dist[node] + it.second;
                q.push({dist[it.first], it.first});
            }
    }
    for(int i=2;i<=N;i++)
        if(dist[i] > Valmax)
            g<<"0 ";
        else
            g<<dist[i]<<' ';
    return 0;
}