#include<iostream>
#include<fstream>
#include<vector>
#define MAX_VAL 20001
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m;
struct vertex{
    int target;
    int cost;
};
vector< vector<vertex> > mat;
vector<int> roads;
vector<bool> viz;
vector<int> viz_stack;
void bfs(int nodee)
{
    int q = 0;
    viz_stack.push_back(nodee);
    int node;
    while(q != viz_stack.size())
    {
        node = viz_stack[q];
        viz[node] = true;
        for(int i=0;i<mat[node].size();i++)
        {
            if(roads[node]+mat[node][i].cost < roads[mat[node][i].target])
            {
                roads[mat[node][i].target] = roads[node]+mat[node][i].cost;
            }
            if(viz[mat[node][i].target] == false) viz_stack.push_back(mat[node][i].target);
        }
        q++;
    }
}
int main()
{
    fin>>n>>m;
    for(int i=0;i<n;i++)
    {
        vector<vertex> a;
        mat.push_back(a);
        roads.push_back(MAX_VAL);
        viz.push_back(0);
    }
    int k1,k2,k3;
    for(int i=0;i<m;i++)
    {
        fin>>k1>>k2>>k3;
        vertex b;
        b.target = k2-1;
        b.cost = k3;
        mat[k1-1].push_back(b);
    }
    roads[0] = 0;
    bfs(0);
    for(int i=1;i<n;i++)
    {
        fout<<roads[i]<<" ";
    }
}