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

void afisare()
{
    int k=0;
    for(int i=1;i<=3;++i)
    {
        for(int j=1;j<=(1<<(i-1));++j)
        {
            ++k;
            cout<<v[heap[k]]<<' ';
        }
        cout<<endl;
    }
}


void up(int poz)
{
    ok=true;
    while(ok)
    {
        ok=0;
        if(v[heap[poz]]<v[heap[poz/2]])
        {
            swap(heap[poz],heap[poz/2]);
            w[poz]=poz;
            w[poz/2]=poz/2;
            ok=1; poz/=2;
        }
    }
}

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

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

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