#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 5e4;
const int MMAX = 25e4;

vector<pair<int, int>> graph[NMAX+1];
int rez[NMAX+1];

void dijkstra(int s){
    set<pair<int, int>> q;
    q.insert({0, s});
    rez[s] = 0;
    while(!q.empty()){
        int cost = q.begin()->first;
        int from = q.begin()->second;
        q.erase(q.begin());
        for(auto ver : graph[from]){
            if(ver.second + cost < rez[ver.first]){
                rez[ver.first] = ver.second + cost;
                q.insert({rez[ver.first], ver.first});
            }
        }
    }
}

int main()
{
    fill(rez+1, rez+1+NMAX, 1e9);
    int n, m;
    f >> n >> m;
    for(int i=1; i<=m; i++){
        int a, b, c;
        f >> a >> b >> c;
        graph[a].push_back({b, c});
    }
    
    dijkstra(1);
    for(int i=2; i<=n; i++)
        if(rez[i] == 1e9)
            g << 0 << ' ';
        else g << rez[i] << ' ';
    
    return 0;
}