#include <iostream>
#include <bits/stdc++.h>
#define N 50005
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<pair<int,int>> graph[N];
priority_queue<pair<int,int>> q;
int viz[N];
int tata[N];
int D[N];
int n,m;

void citire() {
    fin>>n>>m;
    for(int i=1;i<=m;i++) {
        int x,y,c;
        fin>>x>>y>>c;
        graph[x].push_back(make_pair(y,c));
    }

}

void Dijkstra()
{int nod = 1;
    tata[nod] = 0;
    D[nod] = 0;
    q.push(make_pair(0,nod));
    while(!q.empty())
    {
        int nod = q.top().second;
        q.pop();
        if(viz[nod] == 1)
            continue;
        viz[nod] = 1;
        for(int i=0;i<graph[nod].size();i++)
        {
            int vecin = graph[nod][i].first;
            int cost = graph[nod][i].second;
            if(D[vecin] > D[nod] + cost)
            {
                D[vecin] = D[nod] + cost;
                tata[vecin] = nod;
                q.push(make_pair(-D[vecin],vecin));
            }
        }
    }




}



int main() {

    citire();
    for(int i=1;i<=n;i++) D[i] = 1e9;
    Dijkstra();
    for(int i=2;i<=n;i++)
    {  if(D[i] == 1e9) fout<<0<<" ";
        else fout<<D[i]<<" ";
    }

    return 0;
}