/// Dijkstra (N^2 + M)
#include<iostream>
#include<fstream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cassert>
using namespace std;

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

const int N = 50000;
const int MAX_COST = 20000;
const int INF = (N-1) * MAX_COST;

struct node{
    int index;
    int dist = INF;
    bool node_has_been_checked = false;
};

struct edge{
    int from;
    int to;
    int dist;
};

vector<pair<int, int> > neighbours[N]; /// node_index, dist
node nodes[N];
int n,m;

bool check_new_node(){
    /// Find the node
    int best_index = -1;
    int best_cost = INF;
    for(int i=1; i<=n; ++i)
        if(!nodes[i].node_has_been_checked && nodes[i].dist < best_cost){
            best_index = i;
            best_cost = nodes[i].dist;
        }

    /// Assert
    //assert(best_index > -1);
    if(best_index == -1)
        return false;

    /// Visit neighbours and Update their costs
    nodes[best_index].node_has_been_checked = true;
    for(auto &neighbour : neighbours[best_index])
        nodes[neighbour.first].dist = min(nodes[neighbour.first].dist, best_cost + neighbour.second);

    return true;
}

int main()
{
    /// Input
    freopen("dijkstra.out","w",stdout);
    in>>n>>m;
    for(int i=0; i<m; ++i){
        int from, to, dist;
        in>>from>>to>>dist;

        neighbours[from].push_back({to, dist});
    }

    //cout<<n<<" "<<m<<"\n"; for(int i=1; i<=n; ++i) {cout<<i<<": "; for(auto &x : neighbours[i]) cout<<"("<<x.first<<", "<<x.second<<") "; cout<<"\n";}

    /// Solve
    nodes[1].dist = 0;
    for(int i=1; i<=n; ++i)
        if(!check_new_node())
            break;

    /// Print
    for(int i=2; i<=n; ++i)
        cout<<(nodes[i].dist!=INF?(nodes[i].dist):0)<<" ";

    return 0;
}