#include <cstdio>
#include <list>
FILE * fin = fopen("dijkstra.in","r");
FILE * fout = fopen("dijkstra.out","w");

using namespace std;

struct muchie
{
    int y;
    int c;
};

list<muchie> vc[50000];
bool chk[50000];

int hp[50000];
int d[50000];
int pos[50000];
int n;

inline void hp_swap(int a, int b)
{
    hp[a]=hp[a]^hp[b];
    hp[b]=hp[a]^hp[b];
    hp[a]=hp[a]^hp[b];
    pos[hp[a]]=a;
    pos[hp[b]]=b;
}

inline int hp_comp(int a, int b)
{
    return d[hp[a]]<d[hp[b]];
}


void hp_up(int i)
{
    while (i)
    {
        int pos = ((i+1)>>1)-1;
        if (hp_comp(pos,i))
            break;
        hp_swap(i,pos);
        i=pos;
    }
}

void hp_down(int i)
{
    while (1)
    {
        int p1 = (i<<1) + 1;
        int p2 = (i<<1) + 2;
        int min = i;
        if ((p1<n)&&hp_comp(p1,min))
            min=p1;
        if ((p2<n)&&hp_comp(p2,min))
            min=p2;
        if (min==i)
            break;
        hp_swap(i,min);
        i=min;
    }
}

inline int hp_pop()
{
    int res = hp[0];
    n--;
    hp_swap(0,n+1);
    hp_down(0);
    return res;
}

inline void hp_push(int i)
{
    hp[n]=i;
    pos[i]=n;
    n++;
    hp_up(n-1);
}

#define INF 0x3f3f3f3f

int main()
{
    int n,m;
    fscanf(fin,"%d%d",&n,&m);
    ::n=n;
    for (int i=0; i<n; i++)
    {
        hp[i]=i;
        pos[i]=i;
        d[i]=INF;
        chk[i]=0;
    }
    d[0]=0;
    for (int i=0; i<m; i++)
    {
        int x,y,z;
        fscanf(fin,"%d %d %d",&x, &y, &z);
        x--; y--;
        muchie tmp;
        tmp.c=z;
        tmp.y=y;
        vc[x].push_back(tmp);
    }
    for (int i=0; i<n; i++)
    {
        int crnt = hp_pop();
        chk[crnt]=1;
        for (list<muchie>::iterator j=vc[crnt].begin(); j!=vc[crnt].end(); j++)
        {
            int y = (*j).y;
            int c = (*j).c;
            if (chk[y]) continue;
            if (d[crnt]+c<d[y])
            {
                d[y]=d[crnt]+c;
                hp_up(pos[y]);
            }
        }
    }
    for (int i=1; i<n; i++)
        fprintf(fout,"%d ",d[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}