#include <cstdio>
#include <vector>
#include <queue>
#include <string.h>
#define INF 0x3f3f3f3f
using namespace std;

int n,m;
struct GRAF{int nod,cost;GRAF *next;};
typedef GRAF *Graf;
Graf G[50003];
int c[50003];
struct cmp{bool operator()(int x,int y){return x>y;}};
priority_queue<int,vector<int>,cmp> h;

void add(int x,int y,int C)
{
    Graf inter;
    inter=new GRAF;
    inter->nod=y;
    inter->cost=C;
    inter->next=G[x];
    G[x]=inter;
}

int main()
{
    freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
    int x,y,C,i,node;
    scanf("%d %d",&n,&m);
    for(;m;--m)
    {
        scanf("%d %d %d",&x,&y,&C);
        add(x,y,C);
    }
    memset(c,INF,sizeof(c));
    c[1]=0;
    h.push(1);
    while(!h.empty())
    {
        node=h.top();
        for(Graf it=G[node];it;it=it->next)
        if(c[node]+it->cost<c[it->nod])
        {
            c[it->nod]=c[node]+it->cost;
            h.push(it->nod);
        }
        h.pop();
    }
    for(i=2;i<=n;++i)printf("%d ",c[i]);
    printf("\n");
    return 0;
}