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

using namespace std;

bool empt(vector<int> viz)
{
    for (int i=1;i<viz.size();i++) if (viz[i]==0) return false;
    return true;
}

vector <int> c;

void heapify(vector<int> &x,int i)
{
    if (2*i+1<x.size() && c[x[i]]>c[x[i*2+1]])
    {
        int aux=x[i];
        x[i]=x[i*2+1];
        x[i*2+1]=aux;
        heapify(x,2*i+1);
    }
        else if (2*i+2<x.size() && c[x[i]]>c[x[i*2+2]])
        {
            int aux=x[i];
            x[i]=x[2*i+2];
            x[2*i+2]=aux;
            heapify(x,2*i+2);
        }
}

void reverseheapify(vector <int> &x,int i)
{
    if (i>0)
    {
    if (i%2==0 && c[x[i]]>c[x[i/2-1]])
        {
            int aux=x[i];
            x[i]=x[i/2-1];
            x[i/2-1]=aux;
            reverseheapify(x,i/2-1);
        }
        else if (i%2==1 && c[i]>c[i/2])
        {
            int aux=x[i];
            x[i]=x[i/2];
            x[i/2]=aux;
            reverseheapify(x,i/2);
        }
    }
}

int decapitare(vector <int> &x)
{
    int u=x[0];
    x[0]=x[x.size()-1];
    x.erase(x.end()-1);
    heapify(x,0);
    return u;
}

int main()
{
    int 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));
    }
    vector <int> heap,viz;
    viz.resize(n+1);
    for (int i=0;i<n+1;i++) c.push_back(INT_MAX);
    c[1]=0;
    for (int i=0;i<v[1].size();i++)
    {
        c[v[1][i].first]=v[1][i].second;
        heap.push_back(v[1][i].first);
        reverseheapify(heap,i);
    }
    //for (int i=0;i<heap.size();i++) cout<<heap[i]<<" ";
    viz[1]=1;
    while (!empt(viz))
    {
        int u=decapitare(heap);
        viz[u]=1;
        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];
            heap.push_back(v[u][i].first);
            reverseheapify(heap,heap.size()-1);
        }
    }
    ofstream g("dijkstra.out");
    for (int i=1;i<=n;i++) g<<c[i]<<" ";
    return 0;
}