#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;

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){
    viz.assign(n+1, 0);
    dist.assign(n+1, 1e9);
    dist[nod_start] = 0;
    pq.push({dist[nod_start], nod_start});
    while(!pq.empty()){
        pair<int, int> nod_curent = pq.top();
        pq.pop();
        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] == 1e9)
            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);

    return 0;
}