#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 429496729100
#define N 50002
int n,m,nn,h[N],p[N];
vector <int> f[N],v[N];
long long d[N];

void heap_swap(int x,int y)
{
    swap(h[x],h[y]);
    p[h[x]]=x;
    p[h[y]]=y;
}

void heap_up(int k)
{
    if(k>1&&d[h[k]]<d[h[k/2]])
    {
        heap_swap(k,k/2);
        heap_up(k/2);
    }
}

void heap_down(int k)
{
    int f;
    do
    {
        f=0;
        if(k*2<=n)
        {
            f=k*2;
            if(k*2+1<=n&&d[h[f+1]]<d[h[f]])
                f++;
            if(d[h[f]]>=d[h[k]])
                f=0;
        }
        if(f)
            heap_swap(f,k);
    }while(f);
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int i,x,y,k;
    scanf("%d%d",&n,&m);
    nn=n;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&k);
        f[x].push_back(y);
        v[x].push_back(k);
    }
    for(i=1;i<=n;i++)
    {
        h[i]=i;
        d[i]=INF;
        p[i]=i;
    }
    d[1]=0;
    while(n)
    {
        x=h[1];
        heap_swap(1,n);
        n--;
        heap_down(1);
        for(i=0;i<f[x].size();i++)
            if(v[x][i]+d[x]<d[f[x][i]])
            {
                d[f[x][i]]=v[x][i]+d[x];
                heap_up(p[f[x][i]]);
            }
    }
    for(i=2;i<=nn;i++)
        printf("%lld ",d[i]);
    return 0;
}