#include <iostream>
#include <fstream>
#include <climits>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct graf{int nod,val;graf* next;}*a[50001];
int n,m,k,h[50001],p[50001],d[50001];

void add(int from, int to, int cost)
{
    graf *p;
    p=new graf;
    p->val=cost;
    p->nod=to;
    p->next=a[from]; // a[i] toate nodurile la care se ajunge din nodul i
    a[from]=p;
}

void read()
{
    fin>>n>>m;
    for(;m>0;m--)
    {
        int x,y,z;
        fin>>x>>y>>z;
        add(x,y,z);
    }
}
void heap_up(int x)
{
    int t;
    while(x>1)
    {
        t=x>>1; //(x/2)
        if(d[h[t]]>d[h[x]])
        {
            p[h[x]]=t;
            p[h[t]]=x;
            int aux=h[x];
            h[x]=h[t];h[t]=aux;
            x=t;
        }
        else x=1;
    }
}

void downheap(int x)
{
    int f;
    while(x<=k&&f!=x)
    {
        //f=x<<1; (*2)
        f=x;
        if(x<<1<=k)
        {
            f=x<<1;
            if(f+1<=k)
               if(d[h[f+1]]<d[h[f]])f++;
        }
        else return;
        if(d[h[x]]>d[h[f]])
        {
            p[h[x]]=f;
            p[h[f]]=x;
            int aux=h[x];
            h[x]=h[f];h[f]=aux;
            x=f;
        }
        else return;

    }
}

void dijstra()
{
    for(int i=2;i<=n;i++)
        d[i]=INT_MAX,p[i]=-1;
    p[1]=1;h[1]=1;
    k=1;
    while(k)
    {
        int mn=h[1];

        int aux=h[1];
        h[1]=h[k];
        h[k]=aux;

        p[h[1]]=1;
        --k;

        downheap(1);

        graf* q=a[mn];
        while(q)
        {
            if(d[q->nod]>d[mn]+q->val)
            {
                d[q->nod]=d[mn]+q->val;
                if(p[q->nod]!=-1)
                    heap_up(p[q->nod]);
                else
                {
                    h[++k]=q->nod;
                    p[h[k]]=k;
                    heap_up(k);
                }
            }
            q=q->next;
        }
    }
}
int main()
{
    read();
    dijstra();
    for(int i=2;i<=n;i++)
        if(d[i]!=INT_MAX)fout<<d[i]<<' ';
        else fout<<0<<' ';
    return 0;
}