#include <bits/stdc++.h>
using namespace std;
int ans[50010],m,n,i,cost,poz,x,y,z;
bool ap[50010];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
vector<pair<int,int> >v[50010];
pair<int,int>X;
int main()
{
    ifstream f ("dijkstra.in");
    ofstream g ("dijkstra.out");
    f>>n>>m;
    for(i=1; i<=m; ++i)
    {
        f>>x>>y>>z;
        v[x].push_back({y,z});
    }
    for(i=2; i<=n; ++i)
        ans[i]=INT_MAX;
    q.push({0,1});
    while(!q.empty())
    {
        X=q.top();
        cost=X.first;
        poz=X.second;
        q.pop();
        if(ap[poz])continue;
        ap[poz]=true;
        for(i=0; i<v[poz].size(); ++i)
            if(ans[v[poz][i].first]>cost+v[poz][i].second)
            {
                ans[v[poz][i].first]=cost+v[poz][i].second;
                q.push({ans[v[poz][i].first],v[poz][i].first});
            }
    }
    for(i=2; i<=n; ++i)
        if(ans[i]==INT_MAX)g<<0<<" ";
        else g<<ans[i]<<" ";
    return 0;
}