#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

string problema = "dijkstra";

ifstream in(problema+".in");
ofstream out(problema+".out");

struct nodeCost{
    int to;
    int cost;
    nodeCost()
    {
        cost = 0x3f3f3f3f;
    }
};

int n,m;
vector<nodeCost> node[50001];
vector<nodeCost> costs;
int cost[50001];

int main()
{
	in>>n>>m;
    for(int i = 1;i<=m;i++)
    {
        int x,y,c;
        in>>x>>y>>c;
        nodeCost nod;
        nod.cost=c;
        nod.to=y;
        node[x].push_back(nod);
    }
    for(int i = 2;i<=n;i++)
    {
        cost[i]=0x3f3f3f3f;
    }
    nodeCost nod;
    nod.to=1;
    nod.cost=0;
    costs.push_back(nod);
    while(!costs.empty())
    {
        sort(costs.begin(),costs.end(),[](const nodeCost & left, const nodeCost & right)
             {
                return left.cost<right.cost;
             });
        nodeCost minn = costs[0];
        for(nodeCost nod : node[minn.to])
        {
            nodeCost newCost = minn;
            newCost.cost += nod.cost;
            newCost.to=nod.to;
            if(newCost.cost<cost[nod.to])
                cost[nod.to]=newCost.cost;
            costs.push_back(newCost);
        }
        costs.erase(costs.begin());
    }
    for(int i = 2;i<=n;i++)
    {
        out<<cost[i]<<' ';
    }
    return 0;
}