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