#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <deque>
#include <algorithm>
#define ll long long

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct vecin{int nod,cost;} ;
int n,i,j,k,viz[50005],A[50005],poz[50005],temp[50005],m,Size,op,val,x,y,cost,sol[50005],varf,vec,cst;
vector<vecin> v[50005];

void downheap(int nod, int Start, int End)
{
    int left=nod*2;
    int right=nod*2+1;
    int fiu=0;
    int mini=temp[A[nod]];
    if(left<=End && temp[A[left]]<mini) mini=temp[A[left]], fiu=left;
    if(right<=End && temp[A[right]]<mini) mini=temp[A[right]], fiu=right;
    if(fiu)
    {
        swap(poz[A[nod]],poz[A[fiu]]);
        swap(A[nod],A[fiu]);
        downheap(fiu, Start, End);
    }
}

void upheap(int nod, int Start, int End)
{
    int father=nod/2;
    if(nod>=2*Start)
    {
        if(temp[A[father]]>temp[A[nod]])
        {
            swap(poz[A[father]],poz[A[nod]]);
            swap(A[father],A[nod]);
            upheap(father, Start, End);
        }
    }
}

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>cost;
        v[x].push_back({y,cost});
    }
    for(i=2;i<=n;i++) temp[i]=1000000000;
    temp[1]=0;
    for(i=1;i<=n;i++)
    {
        A[i]=i;
        poz[i]=i;
    }
    for(i=n/2;i>=1;i--)
    {
        downheap(i,i,n);
    }
    Size=n;
    while(Size)
    {
        varf=A[1];
        viz[varf]=1;
        sol[varf]=temp[varf];
        swap(poz[A[Size]],poz[A[1]]);
        swap(A[Size],A[1]);
        Size--;
        downheap(1,1,Size);
        for(i=0;i<v[varf].size();i++)
        {
            vec=v[varf][i].nod;
            cst=v[varf][i].cost;
            if(!viz[vec])
            {
                temp[vec]=min(temp[vec],temp[varf]+cst);
                upheap(poz[vec],1,Size);
            }
        }
    }
    for(i=2;i<=n;i++) g<<sol[i]<<' ';
    g<<'\n';
    return 0;
}