#include <bits/stdc++.h>

using namespace std;

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

vector <pair<int,int>> gr[50005];
priority_queue <pair<int,int>> pq;
int dist[50005];

void Dijkstra(int node,int n){
    dist[node] = 0;
    pq.push({-dist[node],node});
    while (!pq.empty()){
        int cnode = pq.top().second;
        int dst = -pq.top().first;
        pq.pop();
        if (dst!=dist[cnode]) continue;
        for (auto vec:gr[cnode]){
            if (dist[vec.first]<=dist[cnode]+vec.second) continue;
            dist[vec.first] = dist[cnode]+vec.second;
            pq.push({-dist[vec.first],vec.first});
        }
    }
}

int main()
{
    int n,m;
    fin >> n >> m;
    for (int i=1;i<=n;++i) dist[i] = 1e9;
    for (int i=1;i<=m;++i){
        int x,y,dst;
        fin >> x >> y >> dst;
        gr[x].push_back({y,dst});
    }
    Dijkstra(1,n);
    for (int i=2;i<=n;++i){
        if (dist[i]==1e9) dist[i] = 0;
        fout << dist[i] << ' ';
    }
    return 0;
}