#include <fstream>
#include <vector>
#include <set>
#include <cstdio>

using namespace std;

const int VAL=50005;
const int INF=2000000000;

int N, M, i, j, cost[VAL], A, B, C, nod;
set < pair <int, int> > Heap;
set < pair <int, int> > :: iterator itH;
vector < pair <int, int> > G[VAL];
vector < pair <int, int> > :: iterator itG;

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d %d", &N, &M);
    for (i=2; i<=N; i++)
    {
        cost[i]=INF;
        Heap.insert({cost[i], i});
    }
    Heap.insert({0, 1});
    for (i=1; i<=M; i++)
    {
        scanf("%d %d %d", &A, &B, &C);
        G[A].push_back({B, C});
    }
    while (Heap.size()>0)
    {
        itH=Heap.begin();
        nod=itH->second;
        Heap.erase(itH);
        for (itG=G[nod].begin(); itG!=G[nod].end(); itG++)
        {
            if (cost[itG->first]>cost[nod]+itG->second)
            {
                itH=Heap.find({cost[itG->first], itG->first});
                Heap.erase(itH);
                cost[itG->first]=cost[nod]+itG->second;
                Heap.insert({cost[itG->first], itG->first});
            }
        }
    }
    for (i=2; i<=N; i++)
    {
        if (cost[i]==INF)
            cost[i]=0;
        printf("%d ", cost[i]);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}