#include <stdio.h>
#define MAX_N  50000
#define MAX_M 250000
#define INF 2000000000
struct nod
{
    int nr;
    int cost;
    nod *next;
}*First[MAX_N+5];
struct heap
{
    int x,cost;
}*Heap;
int N,M,ACN;
int *Distance;
bool *Visited;
void Insert(int x,int y,int cost)
{
    nod *q=new nod;
    q->nr=y;
    q->cost=cost;
    q->next=First[x];
    First[x]=q;
}
void Read()
{
    freopen("dijkstra.in","r",stdin);
    int i,x,y,c;
    scanf("%d %d\n",&N,&M);
    Distance=new int [N+5];
    Visited=new bool [N+5];
    Heap=new heap[M+5];
    ACN=0;
    for(i=1;i<=M;i++)
    {
        scanf("%d %d %d\n",&x,&y,&c);
        Insert(x,y,c);
    }
    fclose(stdin);
}
void Swap(int a,int b)
{
    heap aux=Heap[a];
    Heap[a]=Heap[b];
    Heap[b]=aux;
}
void Up(int cur)
{
    int father=cur/2;
    if(cur==1||Heap[father].cost<=Heap[cur].cost)
        return;
    Swap(father,cur);
    Up(father);
}
int ReturnSon(int father)
{
    int left=2*father;
    int right=2*father+1;
    if(right>ACN)
        return left;
    if(Heap[left].cost<Heap[right].cost)
        return left;
    return right;
}
void Down(int father)
{
    if(2*father>ACN)
        return;
    int son=ReturnSon(father);
    if(Heap[son].cost<Heap[father].cost)
    {
        Swap(father,son);
        Down(son);
    }
}
void Add(int x,int cost)
{
    ACN++;
    Heap[ACN].x=x;
    Heap[ACN].cost=cost;
    Up(ACN);
}
void Delete()
{
    Heap[1]=Heap[ACN];
    ACN--;
    Down(1);
}
int ReturnMin()
{
    int x=Heap[1].x;
    Delete();
    if(ACN<=0)
        return 0;
    if(Visited[x]==1)
        return ReturnMin();
    return x;
}
void Dijkstra(int start)
{
    int i,ac;
    for(i=1;i<=N;i++)
    {
        Visited[i]=0;
        Distance[i]=INF;
    }
    Visited[start]=1;
    Distance[start]=0;
    ac=start;
    nod *q;
    while(ac>0)
    {
        for(q=First[ac];q;q=q->next)
        {
            if(Visited[q->nr]==0&&Distance[q->nr]>Distance[ac]+q->cost)
            {
                Distance[q->nr]=Distance[ac]+q->cost;
                Add(q->nr,Distance[q->nr]);
            }
        }
        ac=ReturnMin();
        Visited[ac]=1;
    }
}
void Write()
{
    int i;
    for(i=2;i<=N;i++)
    {
        if(Distance[i]==INF)
            Distance[i]=0;
        printf("%d ",Distance[i]);
    }
}
int main()
{
    Read();
    Dijkstra(1);
    freopen("dijkstra.out","w",stdout);
    Write();
    fclose(stdout);
    return 0;
}