#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];
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.front().second;
        q.pop();
        if(viz[nod]) continue;
        viz[nod] = 1;
        for(auto it:graph[nod]) {
            int vecin = it.first;
            int cost = it.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;
}