#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>
#include <algorithm>

using namespace std;
#define nmax 50010

int c[nmax],heap[nmax],poz[nmax],dim;

void heapify(int i)
{
    if ( (i*2<=dim && c[heap[i]]>c[heap[i*2]]) || (i*2+1<=dim && c[heap[i]]>c[heap[i*2+1]]) )
    {
        if (c[heap[i*2]] < c[heap[i*2+1]] || i*2+1>dim)
        {
            swap(heap[i],heap[i*2]);
            swap(poz[heap[i]],poz[heap[i*2]]);
            heapify(2*i);
        }
        else
        {
            swap(heap[i],heap[i*2+1]);
            swap(poz[heap[i]],poz[heap[i*2+1]]);
            heapify(2*i+1);
        }
    }
}

void reverseheapify(int i)
{
    if (i>1 && c[heap[i]]<c[heap[i/2]])
    {
        swap(heap[i],heap[i/2]);
        swap(poz[heap[i]],poz[heap[i/2]]);
        reverseheapify(i/2);
    }
}

int decapitare()
{
    int x = heap[1];
    swap(heap[1],heap[dim]);
    swap(poz[heap[1]],poz[heap[dim]]);
    dim--;
    heapify(1);
    return x;
}

int main()
{
    int n,m,a,b,cost,nr=1;
    ifstream f("dijkstra.in");
    f>>n>>m;
    vector<pair<int,int> > v[n+1];
    for (int i=0;i<m;i++)
    {
        f>>a>>b>>cost;
        v[a].push_back(make_pair(b,cost));
    }
    for (int i=2;i<=n;i++)
    {
        c[i]=INT_MAX;
        poz[i]=-1;
    }
    poz[1]=0;
    c[1]=0;
    dim=0;
    for (int i=0;i<v[1].size();i++)
    {
        c[v[1][i].first]=v[1][i].second;
        heap[++dim]=v[1][i].first;
        poz[v[1][i].first]=dim;
        reverseheapify(dim);
    }
    for (int i=1;i<=dim;i++) cout<<heap[i]<<" ";
    while (dim>=1)
    {
        int u=decapitare();
        /*
        cout<<"pasul"<<nr<<endl;
        for (int i=0;i<=dim;i++) cout<<heap[i]<<" ";
        cout<<endl;
        for (int i=1;i<=n;i++) cout<<c[i]<<" ";
        */
        for (int i=0;i<v[u].size();i++)
            if (v[u][i].second+c[u]<c[v[u][i].first])
            {
                c[v[u][i].first]=v[u][i].second+c[u];
                if (poz[v[u][i].first]==-1)
                {
                    heap[++dim]=v[u][i].first;
                    poz[v[u][i].first]=dim;
                    reverseheapify(dim);
                }
                    else reverseheapify(poz[v[u][i].first]);
            }
       /* cout<<endl<<"pasul"<<nr<<endl;
        for (int i=0;i<=dim;i++) cout<<heap[i]<<" ";
        cout<<endl;
        for (int i=1;i<=n;i++) cout<<c[i]<<" ";
       */
        nr++;
    }
    for (int i=2;i<=n;i++) if (c[i]==INT_MAX) c[i]=0;
    ofstream g("dijkstra.out");
    for (int i=2;i<=n;i++) g<<c[i]<<" ";
    return 0;
}