#include <iostream>
#include <fstream>
#include <stdio.h>
#include <list>
#include <vector>
#include <utility>
#include <map>

#define MAXINT (1<<30)
using namespace std;

struct edge
{
    int from,val;
};

typedef list<edge> LIST_OF_EDGES;
typedef vector<LIST_OF_EDGES> VECTOR_OF_LIST_OF_EDGES;
typedef vector<int> VECTOR_OF_INTS;
typedef pair<int,int> PAIR_OF_INTS;
typedef map<PAIR_OF_INTS,int> DIST_MAP;

int find_min(VECTOR_OF_LIST_OF_EDGES &V, DIST_MAP &L,VECTOR_OF_INTS &D, int n, int k)
{
    int minn = MAXINT;
    for(LIST_OF_EDGES::iterator it = V[k].begin(); it != V[k].end(); it++)
    {
        int from = (*it).from;
        int val = (*it).val;
        //PAIR_OF_INTS p(i,k);
        int curr = val + D[from];
        if(curr<minn) minn = curr;
    }

    return minn;
}

VECTOR_OF_INTS shortest_path(VECTOR_OF_LIST_OF_EDGES &V, DIST_MAP &L, int n, int k)
{
    VECTOR_OF_INTS D(n+3,MAXINT);
    D[k] = 0;

    for(int i=1;i<=n;i++)
        if(i!=k)
            D[i] = find_min(V,L,D,n,i);
    return D;
}
int main()
{

    FILE *f = fopen("dijkstra.in","r");
    FILE *g = fopen("dijkstra.out","w");

    int n,m;
    fscanf(f,"%d %d",&n,&m);
    VECTOR_OF_LIST_OF_EDGES V(n+3);
    VECTOR_OF_INTS D(n+3);
    DIST_MAP L;

    for(int i=1;i<=m;i++)
    {
        edge curr;
        int to;
        fscanf(f,"%d %d %d",&curr.from,&to,&curr.val);
        PAIR_OF_INTS p(curr.from,to);
        L[p] = curr.val;
        V[to].push_back(curr);
    }

    for(int i=1;i<=0;i++)
    {
        cout<<i<<": ";
        for(LIST_OF_EDGES::iterator it=V[i].begin(); it != V[i].end(); it++)
            cout<<(*it).from<<" "<<(*it).val<<", ";
        cout<<endl;
    }



    D = shortest_path(V,L,n,1);
    for(int i=2;i<=n;i++)
        if(D[i]==MAXINT)
            fprintf(g,"0 ");
        else
            fprintf(g,"%d ",D[i]);

    fclose(f);
    fclose(g);
    return 0;

}