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

using namespace std;
#define nmax 50000

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

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

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

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

int main()
{
    int nr,n,m,a,b,cost;
    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;
    c[1]=0;
    dim=-1;
    for (int i=0;i<v[1].size();i++)
    {
        c[v[1][i].first]=v[1][i].second;
        heap[++dim]=v[1][i].first;
        reverseheapify(dim);
    }
    viz[1]=1;
    nr=n-1;
    while (nr>0)
    {
        int u=decapitare();
        viz[u]=1;
        //cout<<"pasul"<<n-nr<<endl;
        //for (int i=0;i<=dim;i++) cout<<heap[i]<<" ";
        //cout<<endl;
        //for (int i=0;i<=dim;i++) cout<<c[i]<<" ";
        for (int i=0;i<v[u].size();i++) if (viz[v[u][i].first]!=1)
        {
            if (v[u][i].second+c[u]<c[v[u][i].first])
            {
                c[v[u][i].first]=v[u][i].second+c[u];
                heap[++dim]=v[u][i].first;
                reverseheapify(dim);
            }
        }
        //cout<<endl<<"pasul"<<n-nr<<endl;
        //for (int i=0;i<=dim;i++) cout<<heap[i]<<" ";
       // cout<<endl;
        //for (int i=0;i<=dim;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;
}