#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int NMax=50000;
const int oo=1e9;
vector< pair<int,int> > G[NMax+5];
int N,M;
int D[NMax+5];
int Use[NMax+5];

void Read(){
    fin >> N >> M;
    for(int i=1;i<=M;i++){
        int x,y,c;
        fin >> x >> y >> c;
        G[x].push_back(make_pair(y,c));
    }
}

void Dijkstra(){
    for(int i=2;i<=N;i++){
        D[i]=oo;
    }

    for(int i=1;i<=N;i++){
        int Min=oo, Nod;
        for(int i=1;i<=N;i++){
            if(D[i]<Min && Use[i]==false){
                Min=D[i];
                Nod=i;
            }
        }
        Use[Nod]=true;
        for(auto i:G[Nod]){
            int Vecin=i.first, Cost=i.second;
            D[Vecin]=min(D[Vecin], D[Nod]+Cost);
        }
    }
}

void Print(){
    for(int i=2;i<=N;i++){
        if(D[i]==oo){
            D[i]=0;
        }
        fout << D[i] << " ";
    }
    fout << endl;
}

int main()
{
    Read();
    Dijkstra();
    Print();
}