#include <iostream>
#include <fstream>
#define NMax 60000
#define inf 100000
using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
struct Nod
{
    int nod,cost;
    Nod *next;
};
Nod *t ,*vecin[NMax];
int j,m,n,x,y,costul,nod,d[NMax],coada[5*NMax];
void adauga(int x,int y,int costul)
{
    Nod *q=new Nod;
    q->nod=y;
    q->cost=costul;
    q->next=vecin[x];
    vecin[x]=q;
}
void bellman_fort()
{
    int p,u,i;
    for(i=1;i<=n;i++)
        d[i]=inf;
    p=1;u=1;
    coada[u]=1;
    d[1]=0;
    while(p<=u)
          {
              j=coada[p];p++;
              t=vecin[j];
              while(t)
               {
                if(d[t->nod]>d[j]+t->cost)
                {
                    coada[++u]=t->nod;
                    d[t->nod]=d[j]+t->cost;
                }
                t=t->next;
               }
          }
}
int main()
{
    int i;
    fi>>n>>m;
    for(i=1;i<=m;i++)
    {
        fi>>x>>y>>costul;
        adauga(x,y,costul);
    }
    bellman_fort();
    for(int i=2;i<=n;i++)
        if(d[i]==inf)
        fo<<0<<" ";else fo<<d[i]<<" ";
    return 0;
}