#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,start,finish,cost,l,d,mn,inf=(1<<30);
int v[50005],x,y,c,heap[50005],p[50005];
vector<pair <int,int> >vecini[50005];
bool ok;

void up(int x)
{
    while(v[heap[x]]<v[heap[x/2]])
    {
        swap(p[heap[x]],p[heap[x/2]]);
        swap(heap[x],heap[x/2]);
        x/=2;
    }
}

void down(int x)
{
    heap[1]=heap[l]; --l; p[heap[1]]=1;
    ok=true;
    while(ok==true)
    {
        ok=false; mn=inf;
        if(2*x<=l && v[heap[2*x]]<mn) mn=v[heap[x*2]], d=2*x;
        if(2*x+1<=l && v[heap[2*x+1]]<mn) mn=v[heap[x*2+1]], d=2*x+1;
        if(mn<v[heap[x]])
        {
            ok=true;
            swap(p[heap[x]],p[heap[d]]);
            swap(heap[d],heap[x]);
            x=d;
        }
    }
}

void Dijkstra(int x)
{
    l=n; v[1]=0;
    while(l)
    {
        start=heap[1];
        for(int i=0;i<vecini[start].size();++i)
        {
            finish=vecini[start][i].first;
            cost=vecini[start][i].second+v[start];
            if(cost<v[finish])
            {
                v[finish]=cost;
                up(p[finish]);
            }
        }
        down(1);
    }
}

int main()
{
    f>>n>>m; v[0]=-1;
    for(int i=1;i<=m;++i)
    {
        f>>x>>y>>c;
        vecini[x].push_back(make_pair(y,c));
    }
    for(int i=1;i<=n;++i)
    {
        heap[i]=i; p[i]=i; v[i]=inf;
    }
    Dijkstra(1);
    for(int j=2;j<=n;++j) g<<v[j]<<' ';
    return 0;
}