/// /// /// /// /// /// ///
#include <cstdio>       ///
#include <vector>       ///
#include <queue>        ///
                        ///
#define lim 60000       ///
#define oo ((1<<30) - 1)  ///
/// /// /// /// /// /// ///
using namespace std;

int n,m;

struct nod{

int v; // nodul catre care merge
int cst; // costul

}NOD;
vector <nod> G[lim];


struct dijk_tabel
{

  bool viz; //vizitare
  int  dist;  //distanta

} TBL[lim];

struct compare{
    bool operator() (int a,int b)
    {
        return (TBL[a].dist >= TBL[b].dist);
    }
};


priority_queue <int, vector <int>, compare > Q; //simulare heap


void read()
{
    scanf("%d %d",&n,&m);
    for(int i = 1 ; i <= m ; i++)
        {   int x;
            scanf("%d %d %d",&x,&NOD.v,&NOD.cst);
            G[x].push_back(NOD);
        }
}

void init_Tabel(int start)
{

    TBL[start].viz=1;
    TBL[start].dist=0;
    for(int i = 2 ; i <= n ; i++)
        {

            TBL[i].dist=oo;
        }
}

int start;

void dijkstra()
{
    start=1; // nodul din care plec
    init_Tabel(start);
    Q.push(start);

    while(!Q.empty())
    {
            int min=Q.top();  // indicele minimului din heap
            Q.pop();         // dispare din coada pentru ca nu vom mai avea nevoie de el
            TBL[min].viz=1; //  vizitam nodul al carui vecini ii vom purica

            for(int i=0;i<G[min].size();i++) // parcurgem vecinii nodului
                {   if(!TBL[G[min][i].v].viz) // daca vecinul minimului este NEvizitat
                        {   int sum=TBL[min].dist + G[min][i].cst;
                            if(sum < TBL[G[min][i].v].dist) // daca costul pana la nodul cu pricina este mai mic decat cel actual
                            TBL[G[min][i].v].dist=sum; // actualizam
                            Q.push(G[min][i].v); // bagam in coada vecinul minimului
                        }


                }
    }
}

void write()
{
    for(int i=2;i<=n;i++)
        {

               if(TBL[i].dist==oo)
                {
                    printf("0 ");
                }
                else
                printf("%d ",TBL[i].dist);
            }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    read();
    dijkstra();
    write();

    return 0;
}