#include <fstream>
#define DIM 50005
using namespace std;
struct nod {int x,c;
            nod *urm;} *lst[DIM];
int cost[DIM],q[4*DIM+3];
int n,m;
void add (int a,int b,int c)
{
    nod *p=new nod;
    p->x=b;
    p->c=c;
    p->urm=lst[a];
    lst[a]=p;
}
void read ()
{
    ifstream fin ("dijkstra.in");
    int i,x,y,ct;
    fin>>n>>m;
    for (i=1; i<=m; ++i)
    {
        fin>>x>>y>>ct;
        add (x,y,ct);
    }
}
void solve ()
{
    ofstream fout ("dijkstra.out");
    nod *p;
    int i,in,sf;
    for (q[in=sf=1]=1; in<=sf; ++in)
        for (p=lst[q[in%(4*DIM+3)]]; p; p=p->urm)
            if (!cost[p->x] || cost[q[in%(4*DIM+3)]]+p->c<cost[p->x])
            {
                cost[p->x]=cost[q[in%(4*DIM+3)]]+p->c;
                ++sf;
                q[sf%(4*DIM+3)]=p->x;
            }
    for (i=2; i<=n; ++i)
        fout<<cost[i]<<" ";
}
int main ()
{
    read ();
    solve ();
    return 0;
}