#include <bits/stdc++.h>

using namespace std;

vector<vector<pair<int, int> > > graph;
int n, m;

void read_from_file(){
    ifstream fin("dijkstra.in");

    fin>>n>>m;

    graph.resize(n+1, vector<pair<int, int> >());
    int x, y, c;

    for(int i=1; i<=m; i++){
        fin>>x>>y>>c;
        graph.at(x).push_back(make_pair(y, c));
    }

    fin.close();
}

vector<int> dist;
vector<bool> inCoada;

struct comp{
    bool operator()(int a, int b){
        return dist.at(a) > dist.at(b);
    }
};

priority_queue<int, vector<int>, comp> coada;

void dijkstra(int start){
    dist.resize(n+1, INT_MAX);
    inCoada.resize(n+1, false);

    dist.at(start) = 0;
    coada.push(start);

    while(!coada.empty()){
        int nod = coada.top();
        coada.pop();
        inCoada.at(nod) = false;

        for(auto& vecin:graph.at(nod)){
            if(dist.at(vecin.first) > dist.at(nod)+vecin.second){
                dist.at(vecin.first) = dist.at(nod)+vecin.second;

                if(!inCoada.at(vecin.first)){
                    inCoada.at(vecin.first) = true;
                    coada.push(vecin.first);
                }
            }
        }
    }

}

int main()
{
    read_from_file();
    dijkstra(1);

    ofstream fout("dijkstra.out");

    for(int i=2; i<=n; i++){
        if(dist.at(i)==INT_MAX) fout<<0<<" ";
        else fout<<dist.at(i)<<" ";
    }
}