#include <bits/stdc++.h>
using namespace std;

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

typedef pair<int,int> pr;

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

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

    return 0;
}