//#include <iostream>
//#include <fstream>
//#define inf 1000000000
//#define NMax 50003
//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;
//}
#include<fstream>
#define inf 1000000000
#define NMax 50003
using namespace std;
ifstream f("dijkstra.in");
ofstream g("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_ford(){
    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;
    f>>n>>m;
    for(i=1;i<=m;i++)
     {
        f>>x>>y>>costul;
        adauga(x,y,costul);
     }
    bellman_ford();
    for ( int i = 2; i <= n; i++ )
        if(d[i] == inf) g<<0<<" ";else g<< d[i]<<" ";
    f.close();
    g.close();
}