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

using namespace std;

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

void dijkstra(){
   int i, j, y, c, min;
    bool v[n], r[n];

    for(i=0; i<n; i++)
        v[i]=r[n]=false;
    r[1]=true;

    for(i=0; i<n; i++){
        min = -1;
        for(j=0; j<n; j++)
            if(r[j] && !v[j] && (min==-1 || d[j]<d[min]))
                    min=j;

        //No more nodes
        if(min==-1) return;
        v[min] = true;
        for(auto it=e[min].begin(); it!=e[min].end(); it++){
            y = it->first, c = it->second;
            if(r[y] == false || d[y]>=d[min]+c)
                r[y] = true, d[y]=d[min]+c;
        }
    }
}

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

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

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

    dijkstra();

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

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