#include <iostream>
#include <climits>
#include <cstdlib>
#include <vector>
#include <set>
#include <cassert>
using namespace std;

int *dist;

struct comp
{
    bool operator()(const int &a, const int &b)
    {
        if(dist[a] < dist[b])
            return true;
        if(dist[a] == dist[b])
            return a < b;
        return false;
    }
};

struct Arc
{
    int dest;
    int cost;
};

int main()
{
    Arc temp;
    int N,M;
    int a,b,c;
    int elCur;
    int min = INT_MAX,nodNext;
    FILE *in=fopen("dijkstra.in","r");
    FILE *out=fopen("dijkstra.out","w");
    fscanf(in,"%i %i",&N,&M);
    set<int,comp> s;
    vector <vector<Arc>> g(N);
    dist = (int *)malloc(N * sizeof(int));
    for(int x=0;x<N;x++)
        dist[x] = INT_MAX;
    for(int x=0;x<M;x++)
    {
        fscanf(in,"%i %i %i",&a,&b,&c);
        a--;b--;
        temp.dest = b;
        temp.cost = c;
        g[a].push_back(temp);
    }
    dist[0]=0;
    s.insert(0);
    while(!s.empty())
    {
        printf("\n");

        elCur = *(s.begin()) ;
        s.erase(*(s.begin()));
        //printf("Se relaxeaza %d\n", elCur+ 1);
        for(Arc x:g[elCur])
        {
            if(dist[elCur] + x.cost < dist[x.dest])
            {
                printf("%i -> %i?  %i + %i\n",elCur+1,x.dest+1,dist[elCur],x.cost);
                s.erase(x.dest);
                dist[x.dest] = dist[elCur] + x.cost;
                s.insert(x.dest);
                if(x.dest == 5) {
                    printf("HERE\n");
                    for(auto temp : s)
                        printf("%d ", temp + 1);
                }
            }
        }
    }
    for(int x=1;x<N;x++)
        dist[x]<INT_MAX?fprintf(out,"%i ",dist[x]):fprintf(out,"0 ");
    return 0;
}