#include <iostream>
#include <set>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
#define NMax 50005
int N, M;
int oo=(1<<30);
bool inCoada[NMax];
int dist[NMax];
vector <pair <int,int> > V[NMax];
set <int> S;
void read ()
{
    fin>>N>>M;
    for(int i=1; i<=M; i++) {
        int x,y,c;
        fin>>x>>y>>c;
        V[x].push_back(make_pair(y,c));
    }
    fin.close();
}
void dijkstra (int nodStart)
{
    for(int i=1; i<=N; i++)
        dist[i]=oo;
    S.insert(nodStart);
    inCoada[nodStart]=true;
    dist[nodStart]=0;
    while(!S.empty()) {
        set <int> :: iterator i=S.begin();
        int nodCurent = *i;
        S.erase(S.begin());
        inCoada[nodCurent] = false;
        for(unsigned int j = 0; j<V[nodCurent].size(); j++) {
            int vecin = V[nodCurent][j].first;
            int cost = V[nodCurent][j].second;
            if (dist[nodCurent] + cost < dist[vecin]) {
                dist[vecin] = dist[nodCurent] + cost;
                if(!inCoada[vecin]) {
                    inCoada[vecin]=true;
                    S.insert(vecin);
                }
            }
        }
        //i=S.begin();
        //S.erase(i);
    }
}
int main ()
{
    read();
    dijkstra(1);
    for(int i=2; i<=N; i++)
        if(dist[i]!=oo)
        fout<<dist[i]<<' ';
        else fout<<'0'<<' ';
    return 0;
}