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

using namespace std;

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

struct Edge
{
    int nod,cost;
    Edge(int n,int c);
};

Edge::Edge(int n,int c)
{
    nod=n;
    cost=c;
}

int main()
{
    int n,m,i,j,a,b,c;
    f>>n>>m;
    vector<vector<Edge>>muchie(n+1);
    vector<int>distance(n+1,INT_MAX);
    vector<int>viz(n+1,0);

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

    distance[1]=0;
    for(i=1; i<=n; i++)
    {
        int d_min=INT_MAX,ind=-1;
        for(j=1; j<=n; j++)
            if(viz[j]==0 && distance[j]<d_min)
            {
                d_min=distance[j];
                ind=j;
            }

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

    for(i=2; i<=n; i++)
        g<<distance[i]<<" ";
    return 0;
}