#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector <int> G[100005], Cost[100005];
int N, M;
int NHeap, Heap[100005], Pos[100005];
int D[100005];
bool Use[100005];
void Read()
{
    f >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        int x, y, c;
        f >> x >> y >> c;
        G[x].push_back(y);
        Cost[x].push_back(c);
    }
}
void Swap(int x, int y)
{
    swap(Heap[x], Heap[y]);
    swap(Pos[Heap[x]], Pos[Heap[y]]);
}

void Percolate(int node)
{
    int f = node / 2;
    if(node == 1)
        return;
    if(D[Heap[f]] > D[Heap[node]])
    {
        Swap(node, f);
        Percolate(f);
    }
}

void Sift(int node)
{
    int son = node * 2;
    if(son > NHeap)
        return;
    if(son + 1 <= NHeap && D[son] > D[son + 1])
        son++;
    if(D[node] > D[son])
    {
        Swap(node, son);
        Sift(son);
    }
}
void Insert(int node)
{
    Heap[++NHeap] = node;
    Pos[node] = NHeap;
    Percolate(NHeap);
}

void Erase(int node)
{
    int pos = Pos[node];
    Swap(NHeap, pos);
    --NHeap;
    Percolate(pos);
    Sift(pos);
}
void Solve()
{
    for(int i = 1; i <= N; i++)
        D[i] = 2000000005;
    D[1] = 0;
    for(int i = 1; i <= N; i++)
        Insert(i);
    for(int i = 1; i <= N; i++)
    {
        int node = Heap[1];
        Erase(node);
        Use[node] = 1;
        for(int i = 0; i < G[node].size(); i++)
        {
            int neighb = G[node][i], c = Cost[node][i];
            if(Use[neighb] == 1)
                continue;
            if(D[neighb] > D[node] + c)
            {
                Erase(neighb);
                D[neighb] = D[node] + c;
                Insert(neighb);
            }
        }
    }
    for(int i = 2; i <= N; i++)
    {
        if(D[i] == 2000000005)
            D[i] = 0;
        g << D[i] << " ";
    }

    g << "\n";
}
int main()
{
    Read();
    Solve();
    return 0;
}