#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define nmax 50001
using namespace std;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");
struct arc
{
    int vf, pond;
} a;
vector <arc> la[nmax];
int d[nmax], T[nmax], oo=1<<30, i, j, minim, poz, sursa, n, x, y, z, m;
queue <int> q;
int main()
{f>>n>>m;
sursa=1;
while (f>>x>>y>>z)
    {
        arc a ={y, z};
        la[x].push_back(a);
    }
fill (d, d+nmax, oo);
d[sursa]=0;
q.push(sursa);
while(!q.empty())
{
    int poz = q.front(); q.pop();
    for (j=0 ;j<la[poz].size(); j++)
        {
            int v=la[poz][j].vf;
            int c=la[poz][j].pond;
            if (d[v]>d[poz]+c)
                {
                    d[v]=d[poz]+c;
                    q.push(v);
                }
        }

}

for (i=2; i<=n; i++)
    {
        if (d[i]==oo)
            g<<0<<' ';
        else
            g<<d[i] << ' ';
    }
/*
    for (i=2; i<=n; i++)
    {
        if (d[i]==oo)
            cout<<0<<' ';
        else
            cout<<d[i] << ' ';
    }
    */
    return 0;
}