#include<vector>
#include<list>
#include<fstream>
#include<iostream>
#include<set>

using namespace std;

vector< list<pair<int, int>> > e;
vector<int> d;
set< pair<int, int> > T;
int n, m;

void dijkstra(){
    int x, y, c, val;
    vector<bool> v(n+1, false);
    T.insert(make_pair(0, 1));

    while(T.size() >0){
        x = T.begin()->second;
        T.erase(*T.begin());

        for(auto it=e[x].begin(); it!=e[x].end(); it++){
            y=it->first, c=it->second;
            if(v[y]==false || d[y]>=d[x]+c){
                T.erase(make_pair(d[y], y));
                d[y] = d[x]+c;
                T.insert(make_pair(d[y], y));
                v[y]=true;
            }
        }
    }

}

int main(){
    int i, x, y, c;
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");

    in>>n>>m;
    e.resize(n+1);
    d.resize(n+1);

    for(i=0; i<m; i++)
        in>>x>>y>>c,  e[x].push_back( make_pair(y,c) );

    dijkstra();

    for(i=2; i<=n; i++)
        out<<d[i]<<" ";

    in.close();
    out.close();
    return 0;
}