#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;
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(int poz)
{
    if (viz[poz])
        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);
        }
    }
    pair<int,int> dem=V[0];
    pop_heap(V.begin(),V.end());
    V.pop_back();
    dji(dem.second);
}
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;
    dji(1);
    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;
}