#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
///DIJKSTRA
using namespace std;

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

const int NMax=50005;
const int oo = (1 << 30);

int N,M;
int D[NMax];

bool InCoada[NMax];

struct comparaDist{
    bool operator()(int x, int y){
        return D[x]>D[y];
    }
};

vector <pair <int, int> > G[NMax];
priority_queue <int, vector < int >, comparaDist >coada;

void cit(){
    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 afisare(){
    for (int i = 2; i <= N; i++){
        if (D[i]!=oo)
            fout<<D[i]<<" ";
        else fout<<0<<" ";
    }
}
void Dijkstra(int start){
    for (int i=1; i<=N; i++)
        D[i]=oo;
    D[start]=0;
    coada.push(start);
    InCoada[start]=true;
    while (!coada.empty()){
        int curent=coada.top();
        coada.pop();
        InCoada[curent]=false;
        for (unsigned int i = 0; i < G[curent].size(); i++)
        {
            int vecin=G[curent][i].first;
            int cost=G[curent][i].second;
            if (D[curent]+cost < D[vecin]){
                D[vecin]=D[curent]+cost;
                if (InCoada[vecin]==false)
                {
                    coada.push(vecin);
                    InCoada[vecin]=true;
                }
            }
        }
    }
}
int main()
{
    cit();
    Dijkstra(1);
    afisare();
    return 0;
}