#include <bits/stdc++.h>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,x,y,dist[50005],nod,cost,i,nod1,sel[50005],nr;
vector <pair <int,int> > v[50005];
pair <int,int> acum;
priority_queue <pair <int,int>, vector <pair <int,int > >  , greater  < pair <int,int> > > h;
int main()
{
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>x>>y>>cost;
        v[x].push_back({y,cost});
    }
    for (i=1;i<=n;i++)
    {
        dist[i]=-1;
    }
    dist[1]=0;
    for (i=0;i<v[1].size();i++)
    {
        int nod=v[1][i].first;
        dist[nod]=dist[1]+v[1][i].second;
        h.push({dist[nod],nod});
    }
    nr=v[1].size();
    while (nr)
    {
        while (!h.empty()&&sel[h.top().second]==1)
        {
            h.pop();
        }
        acum=h.top();
        h.pop();
        sel[nod]=1;
        nr--;
        nod=acum.second;
        cost=acum.first;
        for (i=0;i<v[nod].size();i++)
        {
            nod1=v[nod][i].first;
            if (dist[nod1]==-1)
            {
                nr++;
                dist[nod1]=cost+v[nod][i].second;
                h.push({dist[nod1],nod1});
            }
            else
            if (dist[nod1]>cost+v[nod][i].second)
            {
                dist[nod1]=cost+v[nod][i].second;
                h.push({dist[nod1],nod1});
            }
        }
    }
    for (i=2;i<=n;i++)
    {
        if (dist[i]==-1)
        {
            g<<"0"<<" ";
        }
        else
        {
            g<<dist[i]<<" ";
        }
    }
    return 0;
}