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

using namespace std;
#define nmax 50010

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

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

void reverseheapify(int i)
{
    if (i>0 && c[heap[i]]<c[heap[i/2]])
        {
            int aux=heap[i];
            heap[i]=heap[i/2];
            heap[i/2]=aux;
            aux=poz[i];
            poz[i]=poz[i/2];
            poz[i/2]=aux;
            reverseheapify(i/2);
        }
}

int decapitare()
{
    int u=heap[1];
    heap[1]=heap[dim];
    poz[heap[1]]=1;
    dim--;
    heapify(1);
    viz[u]=1;
    return u;
}

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++)
    {
        viz[i]=0;
        c[i]=INT_MAX;
        poz[i]=-1;
    }
    viz[1]=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>=0)
    {
        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 if (viz[v[u][i].first]==0) 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;
}