#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<<" ";
            continue;
        }
        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;}