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

using namespace std;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

struct Edge
{
    int cost,nod;
    Edge(int cost1,int nod1);
};

Edge::Edge(int cost1,int nod1)
{
    cost=cost1;
    nod=nod1;
}

int main()
{
    int n,m,i,j,c,a,b,vmin,ind,inf;
    f>>n>>m;
    inf=(n-1)*20000;
    vector<vector<Edge>>G(n+1);
    vector<int>d(n+1,inf);
    vector<int>viz(n+1,0);

    for(i=1; i<=m; i++)
    {
        f>>a>>b>>c;
        G[a].push_back(Edge(c,b));
    }

    d[1]=0;
    for(i=1; i<n; i++)
    {
        vmin=inf;
        ind=-1;
        for(j=1; j<=n; j++)
            if(viz[j]==0 && d[j]<vmin)
            {
                vmin=d[j];
                ind=j;
            }
        if(ind==-1) // nu toate nodurile sunt accesibile => la un moment dat nu mai gaseste noduri cu d[nod]<inf => ind=-1 =>incearca sa relaxeze -1 => crapa
            break;

        for(auto edge:G[ind])
            if(d[edge.nod]>d[ind]+edge.cost)
                d[edge.nod]=d[ind]+edge.cost;
        viz[ind]=1;
    }

    for(i=2; i<=n; i++)
    {
        if(d[i]==inf)
            d[i]=0;
        g<<d[i]<<" ";
    }
    return 0;
}