#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

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

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> Q;

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));
    }
}

int FindMin(){
    while(Used[Q.top().second])
        Q.pop();
    int res = Q.top().second;
    Q.pop();
    return res;
}

void Dijkstra(){
    for(int i=2;i<=N;i++){
        D[i]=oo;
    }
    for(int i = 1; i <= N; i++){
        Q.push(make_pair(D[i], i));
    }
    for(int i=1;i<=N;i++){
        int Nod;
        Nod=FindMin();
        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();
}