#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct Node
{
    int x,cost;
    Node()
    {
        this->x = 0;
        this->cost = 0;
    }
    Node(int x, int cost)
    {
        this->x = x;
        this->cost = cost;
    }
};

const int INF = 2000000000;
int d[50010];
int H[50010];
int nh;
int pozitieInHeap[50010];
int N, M;
vector <Node> G[50010];


void Read()
{
    ifstream f("dijkstra.in");
    f >> N >> M;
    for (int i = 1; i <= M; ++ i)
    {
        int cost, x, y;
        f >> x >> y >> cost;
        G[x].push_back(Node(y, cost));
    }
    f.close();
}

int Father(int x)
{
    return x / 2;
}

int LeftSon(int x)
{
    return x * 2;
}

int RightSon(int x)
{
    return x * 2 + 1;
}

void UpHeap(int poz)
{
    while(poz > 1)
    {
        if(d[H[poz]] < d[H[Father(poz)]])
        {
            swap(pozitieInHeap[H[poz]], pozitieInHeap[H[Father(poz)]]);
            swap(H[poz], H[Father(poz)]);
            poz = Father(poz);
        }
        else
            break;
    }
}

void DownHeap(int poz)
{
    while(true)
    {
        int minSon = LeftSon(poz);

        if(minSon <= nh)
        {
            if (RightSon(poz) <= nh && d[H[RightSon(poz)]] < d[H[LeftSon(poz)]])
                minSon = RightSon(poz);
            if (d[H[poz]] > d[H[minSon]])
            {
                swap(pozitieInHeap[H[poz]], pozitieInHeap[H[minSon]]);
                swap(H[poz], H[minSon]);
                poz = minSon;
            }
            else
                break;
        }
        else
            break;
    }
}

void InsertInHeap(int nod)
{
    H[++nh] = nod;
    pozitieInHeap[nod] = nh;
    UpHeap(nh);
}

void DeleteMin()
{
    H[1] = H[nh];
    pozitieInHeap[H[nh]] = 1;
    nh--;
    DownHeap(1);
}

int ExtractMin()
{
    return H[1];
}

void Solve()
{
    for (int i = 1; i <= N; ++ i)
        d[i] = INF;
    d[1] = 0;
    for (int i = 1; i <= N; ++ i)
    {
        InsertInHeap(i);
    }
    for (int i = 1; i < N; ++ i)
    {
        int bestNode = ExtractMin();
        DeleteMin();
        for (vector <Node> :: iterator it = G[bestNode].begin(); it != G[bestNode].end(); ++ it)
        {
            if (d[bestNode] + it->cost < d[it->x])
            {
                d[it->x] = d[bestNode] + it->cost;
                UpHeap(pozitieInHeap[it->x]);
                DownHeap(pozitieInHeap[it->x]);
            }
        }
    }
}

void Write()
{
    ofstream g("dijkstra.out");
    for(int i = 2; i <= N; ++ i)
    {
        if (d[i] == INF)
            g<<"0 ";
        else
            g<<d[i]<<" ";
    }
    g.close();
}


int main()
{
    Read();
    Solve();
    Write();
    return 0;
}