#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
#define inf 2000000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,nr=0;
vector <pair<int,int> > V;
vector <pair<int,int> > A[50100];
int D[50100];
int poz[50100];
int viz[50100];
bool cmp(pair<int,int> x,pair<int,int> y)
{
    return x.first>y.first;
}
void dji()
{
    if (V.empty())
        return;
    pair<int,int> dem=V[0];
    int poz=dem.second;
    pop_heap(V.begin(),V.end(),cmp);
    V.pop_back();
    nr++;
    if (viz[poz] || nr>n)
        return;
    viz[poz]=1;
    for (vector <pair<int,int> >::iterator it = A[poz].begin(); it!=A[poz].end(); it++)
    {
        if (D[poz]+it->second<D[it->first] && viz[it->first]==0)
        {
            D[it->first]=D[poz]+it->second;
            V.push_back(make_pair(D[it->first],it->first));
            push_heap(V.begin(),V.end(),cmp);
        }
    }

    dji();
}
int main()
{
    fin>>n>>m;
    make_heap(V.begin(),V.end(),cmp);
    for (int i=1; i<=m; i++)
    {
        int x,y,z;
        fin>>x>>y>>z;
        A[x].push_back(make_pair(y,z));
    }
    for (int i=1; i<=n; i++)
        D[i]=inf;
    D[1]=0;
    V.push_back(make_pair(0,1));
    push_heap(V.begin(),V.end(),cmp);
    dji();
    V.erase(V.begin(),V.end());
    for (int i=2; i<=n; i++)
    {
        if (D[i]==inf)
            fout<<"0 ";
        else
            fout<<D[i]<<' ';
    }
    return 0;
}