#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
//#include <Windows.h>

using namespace std;

int N,M,D[50005];
queue<int> Q;
vector<pair<int,int>> G[50005];

void Read(){
    ifstream fin("dijkstra.in");
    fin >> N >> M;
    for(int i=0;i<M;i++){
        int x,y,z;  fin >> x >> y >> z;
        G[x].push_back(make_pair(y,z));
        //G[y].push_back(make_pair(x,z));
    }
}

void setmet(int D[]){
    for(int i=0;i<=N;i++)
        D[i]=-1;
}

void dijkstra(int Nod){
    setmet(D); D[Nod]=0;
    Q.push(Nod);
    while(!Q.empty()){
        Nod=Q.front(); Q.pop();
        for(int i=0;i<G[Nod].size();i++){
            int vecin=G[Nod][i].first,dist=G[Nod][i].second;
            if(D[vecin]>D[Nod]+dist || D[vecin]==-1){
                D[vecin]=D[Nod]+dist;
                Q.push(vecin);
            }
        }
    }
}

void Print(){
    ofstream fout("dijkstra.out");
    for(int i=2;i<=N;i++)
        if(D[i]!=-1)
            fout << D[i] << ' ';
        else
            fout << 0 << ' ';
}

int main()
{
    Read();
    dijkstra(1);
    Print();
    return 0;
}