#include <bits/stdc++.h>

using namespace std;

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

vector <pair<int,int>> vecin[50005];
priority_queue <pair<int,int>> q;
int dist[50005];

void Dijkstra(int node,int NrNodes){
    dist[node] = 0;
    q.push({-dist[node],node});
    while (!q.empty()){
        int cnode = q.top().second;
        int ds = -q.top().first;
        q.pop();
        if (ds!=dist[cnode]) continue;
        for (int i=0;i<vecin[cnode].size();++i){
            if (dist[vecin[cnode][i].first]<=dist[cnode]+vecin[cnode][i].second) continue;
            dist[vecin[cnode][i].first] = dist[cnode]+vecin[cnode][i].second;
            q.push({-dist[vecin[cnode][i].first],vecin[cnode][i].first});
        }
    }
    for (int i=2;i<=NrNodes;++i){
        if (dist[i]==1000000) dist[i] = 0;
        fout << dist[i] << ' ';
    }
}

int main()
{
    int NrNodes,NrEdges;
    fin >> NrNodes >> NrEdges;
    for (int i=1;i<=NrNodes;++i) dist[i] = 1000000;
    for (int i=1;i<=NrEdges;++i){
        int x,y,dst;
        fin >> x >> y >> dst;
        vecin[x].push_back({y,dst});
    }
    Dijkstra(1,NrNodes);
    return 0;
}