#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

string problema = "bellmanford";

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

int n,m;
struct nodeCost{
    int to;
    int cost;
};
vector<nodeCost> nod[50001];
queue<int> toVisit;
int cost[50001];
int timesPassed[50001];

int main()
{
	in>>n>>m;
	for(int i = 1;i<=m;i++)
    {
        int x,y,c;
        in>>x>>y>>c;
        nodeCost node;
        node.cost=c;
        node.to=y;
        nod[x].push_back(node);
    }
    for(int i = 2;i<=n;i++)
    {
        cost[i]=(1<<30);
    }
    toVisit.push(1);
    while(!toVisit.empty())
    {
        for(nodeCost node : nod[toVisit.front()])
        {
            if(timesPassed[node.to]<n)
            {
                timesPassed[node.to]++;
                int newCost = cost[toVisit.front()]+node.cost;
                if(newCost<cost[node.to])
                {
                    cost[node.to]=newCost;
                    toVisit.push(node.to);
                }
            }
        }
        toVisit.pop();
    }
    for(int i = 2;i<=n;i++)
    {
        out<<cost[i]<<' ';
    }
    return 0;
}