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

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

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

int main()
{
    int n,m,i,a,b,c;
    f>>n>>m;
    vector<vector<Edge>>muchii(m);
    vector<int>distance(n+1,n+1);
    set<pair<int,int>>Q;

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

    distance[1]=0;
    for(i=1; i<=n; i++)
        Q.insert(make_pair(distance[i],i));

    while(!Q.empty())
    {
        int u=(*Q.begin()).second;
        for(auto v:muchii[u])
            if(distance[v.nod]>distance[u]+v.cost)
            {
                Q.erase(make_pair(distance[v.nod],v.nod));
                distance[v.nod]=distance[u]+v.cost;
                Q.insert(make_pair(distance[v.nod],v.nod));
            }
        Q.erase(Q.begin());
    }

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

    return 0;
}