#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#define INF 10000000
#define Nrmax 50004



using namespace std;


int d[Nrmax];
vector < pair<int,int> >graf[Nrmax];

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

void Dijkstra(set<pair<int,int> >nod)
{
    int v,c,node,dist;
    while(!nod.empty()){
        node=nod.begin()->second;
        dist=nod.begin()->first;
        nod.erase(nod.begin());
        for(int i=0;i<graf[node].size();i++)
        {
            v = graf[node][i].first;
            c = graf[node][i].second;
            if(d[v] > d[node]+c)
            {
                if(d[v]!=INF)
                    nod.erase(nod.find(pair<int,int>(d[v], v)));
                d[v] = d[node]+c;
                nod.insert(pair<int,int>(d[v],v));

            }
        }
    }
}

int main()
{
    int n,m;
    int node, vecin, cost;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        {
            fin>>node>>vecin>>cost;
            graf[node].push_back(pair<int,int> (vecin, cost));
        }
    set<pair<int,int> >nod;
    d[1]=0;
    nod.insert(make_pair(0,1));
    for(int i=2;i<=n;i++)
        d[i]=INF;
    Dijkstra(nod);
    for(int i=2;i<=n;i++)
        if(d[i]==INF)
            fout<<0<<" ";
        else
            fout<<d[i]<<" ";
    fin.close();
    fout.close();
    return 0;
}