#include <fstream>
#include <vector>
#include <queue>
//#include <algorithm>
#include <string.h>

using namespace std;

fstream f("dijkstra.in",ios::in);
fstream g("dijkstra.out",ios::out);

const int nmax=50001,INF=0x3f3f3f3f;

struct dat
{
    int leg,cost;
};

vector < dat > a[nmax];
queue <int> q;

int i,j,x,b,c,n,m,nc;

int dist[nmax],viz[nmax];

void citire()
{
    f>>n>>m;
    dat cit;
    for (i=1;i<=m;i++)
    {
        f>>x>>cit.leg>>cit.cost;
        a[x].push_back(cit);
    }
}

void rezolvare()
{
    memset(dist,INF, sizeof(dist));
    memset(viz,0,sizeof(viz));
    q.push(1);
    viz[1]=1;
    dist[1]=0;
    while (!q.empty())
    {
        nc=q.front();
        q.pop();
        viz[nc]=0;
        for (vector<dat>::iterator it=a[nc].begin();it!=a[nc].end();++it)
            if (dist[nc]+it->cost<dist[it->leg])
            {
                dist[it->leg]=dist[nc]+it->cost;
                if (!viz[it->leg])
                {
                    q.push(it->leg);
                    viz[it->leg]=1;
                }
            }
    }
}

void scriere()
{
    for (i=2;i<=n;i++) g<<((dist[i]<INF)?dist[i]:0)<<" ";
}

int main()
{
    citire();
    rezolvare();
    scriere();
    f.close();g.close();
    return 0;
}