#include <bits/stdc++.h>

using namespace std;

string file="dijkstra";
ifstream fin(file+".in");
ofstream fout(file+".out");

#define inf 2000000
vector<pair<int, int> > g[50005];
int n, m;
set<pair<int, int> > s;
int dist[50005];
int main()
{
    fin>>n>>m;
    while (m){
        m--;
        int x, y, z;
        fin>>x>>y>>z;
        g[x].push_back({y, z});
    }
    dist[1]=0;
    fill(dist+2, dist+n+2, inf);
    s.insert({0, 1});
    while (!s.empty()){
        int nod=s.begin()->second;
        s.erase(s.begin());
        for (auto it:g[nod]){
            if (dist[it.first]>dist[nod]+it.second){
                s.erase({dist[it.first], it.first});
                dist[it.first]=dist[nod]+it.second;
                s.insert({dist[it.first], it.first});
            }
        }
    }
    for (int i=2; i<=n; i++){
        if (dist[i]!=inf)fout<<dist[i]<<" ";
        else fout<<0;
    }
    return 0;
}