#include <stdio.h>
#include <string.h>
#include <vector>
#define INF 0x3f
#define infve 1061109567

using namespace std;

struct vecin
{
    int nod,cost;
}auxve;

int n,m,nh;
int d[50001],heap[50001],poz[50001];
vector<vecin> v[50001];
vector<vecin>::const_iterator itr,fin;

void swag(int i,int j) //u don't have it
{
    int aux;
    aux=heap[j];
    heap[j]=heap[i];
    heap[i]=aux;
    poz[heap[j]]=i;
    poz[heap[i]]=j;
}

void heapup(int k)
{
    int j,aux;
    while(k>1)
    {
        j=k/2;
        if(d[heap[j]]>d[heap[k]]) {swag(j,k);k=j;}
        else break;
    }
}

int heapout()
{
    int j,k,i=1;
    swag(1,nh);
    nh--;
    while(2*i<=nh)
    {
        j=2*i;
        if(d[heap[j]]>d[heap[j+1]]&&j+1<=nh) j++;
        if(d[heap[i]]>d[heap[j]]) {swag(i,j);i=j;}
        else break;
    }
    return heap[nh+1];
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int i,j,a;
    memset(d,INF,sizeof(d));
    d[1]=0;
    scanf("%d%d",&n,&m);
    nh=n;
    for(i=0;i<m;i++)
    {
        scanf("%d%d%d",&a,&(auxve.nod),&(auxve.cost));
        v[a].push_back(auxve);
    }
    for(i=1;i<=n;i++)
    {
        heap[i]=i;
        poz[i]=i;
        heapup(i);
    }

    while(nh>0)
    {
        i=heapout();
        itr=v[i].begin();
        fin=v[i].end();
        for(;itr!=fin;itr++)
        {
            if(d[(*itr).nod]>d[i]+(*itr).cost)
            {
                d[(*itr).nod]=d[i]+(*itr).cost;
                heapup(poz[(*itr).nod]);
            }
        }
    }

    for(i=2;i<=n;i++)
    {
        if(d[i]!=infve) printf("%d ",d[i]);
        else printf("0 ");
    }

    return 0;
}