#include <bits/stdc++.h>

using namespace std;

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

int i,j,n,p,dist[50005],a,b,val,viz[50005],nod,vecin,m;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
vector <pair<int,int>> v[50005];

int main()
{
fin>>n>>m;
for(i=1;i<=n;i++){
    dist[i] = 1000000000;
}
for(i=1;i<=m;i++){
    fin>>a>>b>>val;
    v[a].push_back({b,val});
}
p = 1;
pq.push({0,p});
dist[p] = 0;
while(!pq.empty()){
    nod = pq.top().second;
    val = pq.top().first;
    //vecin
    if(!viz[nod]){
    for(i=0;i<v[nod].size();i++){
        vecin = v[nod][i].first;
        if(val + v[nod][i].second < dist[vecin]){
            dist[vecin] = val + v[nod][i].second;
            pq.push({dist[vecin],vecin});
        }
    }
    viz[nod] = 1;
    }
    pq.pop();
}
for(i=2;i<=n;i++){
    if(dist[i] == 1000000000)
       dist[i] = 0;
    fout << dist[i] << " ";
}
    return 0;
}