#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n,i,j,p,q,nr,hs,m,l;
int d[50005];
struct nod
{
    int y;
    int cost;
}H[250005],el,El;
vector < nod > v[50005];
void citire()
{
    int a,b,c;
    scanf("%d %d",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        el.y=b; el.cost=c;
        v[a].push_back(el);
    }
}
int father(int x)
{
    return x/2;
}
int left_son(int x)
{
    return 2*x;
}
int right_son(int x)
{
    return 2*x+1;
}
void sift(int N,int K)
{
    int son=0;
    do
    {
        if (left_son(K)<=N) son=left_son(K);
        if ((right_son(K)<=N)&&(H[right_son(K)].cost<H[son].cost)) son=right_son(K);
        if ((H[son].cost>=H[K].cost)) son=0;
        if (son)
        {
            swap(H[K],H[son]);
            K=son;
        }
    }while (son);
}
void percolate(int N,int K)
{
    nod k=H[K];
    while ((K>=1)&&(k.cost<H[father(K)].cost))
    {
        H[K]=H[father(K)];
        K=father(K);
    }
    H[K]=k;
}
void insert(int& N, nod k) {
    H[++N]=k;
    percolate(N,N);
}
void cut(int& N, int K)
{
    H[K]=H[N];
    --N;
    if ((K>1)&&(H[K].cost<H[father(K)].cost)) {
        percolate(N,K);
    } else {
        sift(N,K);
    }
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire(); el.y=1; el.cost=0; hs=0;
    insert(hs,el);
    for (i=1;i<=n;i++) d[i]=1<<30;
    while (hs)
    {
        el=H[1];
        cut(hs,1);
        if (d[el.y]==1<<30)
        {
            d[el.y]=el.cost;
            l=v[el.y].size();
            for (i=0;i<l;i++) if ((v[el.y][i].cost+d[el.y]<d[v[el.y][i].y]))
            {
                El=v[el.y][i]; El.cost=v[el.y][i].cost+d[el.y];
                insert(hs,El);
            }
        }
    }
    for (i=2;i<=n;i++) {if (d[i]==1<<30) d[i]=0; printf("%d ",d[i]);}
    return 0;
}