#include <bits/stdc++.h>
#define NMAX 50005
#define inf 1e9
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector<pair<int,int> >v[NMAX];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >h;
bool use[NMAX];
int d[NMAX],n,m,i,j,x,y,c,nod,vecin;
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        v[x].push_back({y,c});
    }
    for(i=1;i<=n;i++)
        d[i]=inf;
    d[1]=0;
    h.push({0,1});
    while(!h.empty())
    {
        nod=h.top().second;
        h.pop();
        if(!use[nod])
        {
            for(i=0;i<v[nod].size();++i)
            {
                vecin=v[nod][i].first;
                if(d[nod]+v[nod][i].second<d[vecin])
                {
                    d[vecin]=d[nod]+v[nod][i].second;
                    h.push({d[vecin],vecin});
                }
            }
        }
        use[nod]=true;
    }
    for(i=2;i<=n;i++)
    {
        if(d[i]==inf)g<<"0"<<" ";
        else g<<d[i]<<" ";
    }
    return 0;
}