#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int inf = (1 << 31) - 1;

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

vector<vector<pair<int,int>>>  adj_list;
vector<int> viz;
vector<int> dist;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

int n,m;

void dijkstra(int nod_start, int n){
    viz.assign(n+1,0);
    dist.assign(n+1,inf);
    dist[nod_start] = 0;
    pq.push({dist[nod_start], nod_start});
    while(!pq.empty()){
        pair<int,int> nod_curent = pq.top();
        pq.pop();
        if(viz[nod_curent.second])
            continue;
        viz[nod_curent.second] = 1;
        for(auto &v : adj_list[nod_curent.second]){
            if(!viz[v.first]){
                if(dist[v.first] > dist[nod_curent.second] + v.second){
                    dist[v.first] = dist[nod_curent.second] + v.second;
                    pq.push({dist[v.first], v.first});
                }
            }
        }
    }
    for(int i = 2; i <= n; i++){
        if(dist[i] == inf)
            fout << 0 << " ";
        else
            fout << dist[i] << " ";
    }
}

int main()
{
    fin >> n >> m;
    adj_list.assign(n+1,{});

    for(int i = 0; i < m; i++){
        int x,y,c;
        fin >> x >> y >> c;
        adj_list[x].push_back({y,c});
    }

    dijkstra(1,n);

    return 0;
}