#include<bits/stdc++.h>
using namespace std;
ifstream F("dijkstra.in");
ofstream G("dijkstra.out");
#define P pair<int,int>
priority_queue<P,vector<P>,greater<P> > q;
vector<P> u[50001];
int n,m,i,j,k,d[50001];
int main()
{
    for(F>>n>>m;m--;F>>i>>j>>k,u[i].push_back({j,k}));
    for(i=2;i<=n;d[i++]=1e9);
    for(q.push({0,1});!q.empty();q.pop())
        for(i=q.top().second,k=u[i].size(),j=0;j<k;++j)
            if(d[u[i][j].first]>d[i]+u[i][j].second)
                d[u[i][j].first]=d[i]+u[i][j].second,q.push({d[u[i][j].first],u[i][j].first});
    for(i=2;i<=n;G<<(d[i]==1e9?0:d[i])<<' ',++i);
    return 0;
}