/// /// ///
#include <cstdio>
#include <vector>
#include <queue>

#define lim 50001
#define oo 0X3f3f3f
/// /// ///
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
  int  t; // tatal -> t[i] -> de unde vine nodul I

} 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;
    TBL[start].t=0;

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

void write()
{
    for(int i=1;i<=n;i++)
        {
            if(i!=start)
            {
                printf("%d ",TBL[i].dist);
            }
        }
}

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

    return 0;
}