#include <fstream>
#include <queue>
#define lg_max 50001
#define infinit 0x3f3f3f

using namespace std;

ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

struct nod
{
    int inf,cost;
    nod *next;
} *sir[lg_max];

int n,m,dist[lg_max],viz[lg_max];
queue < int > C;

void adauga(int x,int y,int c)
{
    nod *w=new nod;
    w->inf=x;
    w->cost=c;
    w->next=sir[y];
    sir[y]=w;
}

void citire()
{
    fin>>n>>m;
    int a,b,cost;
    for (int i=0;i<m;i++)
    {
        fin>>a>>b>>cost;
     //   adauga(a,b,cost);
        adauga(b,a,cost);
    }
    memset(dist,infinit,sizeof dist);
    memset(viz,0,sizeof(viz));
}

void BF()
{
    dist[1]=0;
    C.push(1);
    viz[1]=1;
    while(!C.empty())
    {
        int min=C.front();
        C.pop();
        viz[min]=0;
        for (nod *i=sir[min];i;i=i->next)
        if (dist[i->inf]>dist[min]+i->cost)
        {
            dist[i->inf]=dist[min]+i->cost;
            if (viz[i->inf]!=1)
            {
                C.push(i->inf);
                viz[i->inf]=1;
            }
        }
    }
}

void afisare()
{
    for (int i=2;i<=n;i++)
        fout<<((dist[i]==infinit)?0:dist[i])<<" ";
    fout<<"\n";
}

int main ()
{
    citire();
    BF();
    afisare();
    return 0;
}