#include <fstream>
#include <vector>
using namespace std;

const int NMAX = 1<<16;
const int MMAX = 250001;
const int INF = 1<<30;

int N, heap_size, M;
vector<int> G[NMAX], cost[NMAX];
int heap[NMAX], pos[NMAX];
int d[NMAX];

void citire()
{
    ifstream in("dijkstra.in");
    in>>N>>M;
    for (int i=0; i<M; ++i)
    {
        int a, b, c;
        in>>a>>b>>c;
        G[a].push_back(b);
        cost[a].push_back(c);
    }
    in.close();
}

inline void swap(int &a, int &b)
{
    a ^= b;
    b ^= a;
    a ^= b;
}

inline int father(const int &node)
{
    return (node>>1);
}

inline int leftSon(const int &node)
{
    return (node<<1);
}

inline int rightSon(const int &node)
{
    return 1 + (node<<1);
}

void sift(int node)
{
    while (node <= heap_size)
    {
        int son = node;
        int left_son = leftSon(node);
        int right_son = rightSon(node);
        if (left_son <= heap_size)
        {
            son = left_son;
            if (right_son<=heap_size && d[heap[right_son]]<d[heap[son]])
                son = right_son;
        }
        if (d[heap[son]] < d[heap[node]])
        {
            pos[heap[son]] = node;
            pos[heap[node]] = son;
            swap(heap[son], heap[node]);
            node = son;
        }
        else node = heap_size + 1;
    }
}

void percolate(int node)
{
    while (node > 1)
    {
        int _father = father(node);
        if (d[heap[node]] < d[heap[_father]])
        {
            pos[heap[node]] = _father;
            pos[heap[_father]] = node;
            swap(heap[node], heap[_father]);
            node = _father;
        }
        else node = 1;
    }
}

void insert(const int &node)
{
    if (pos[node] == 0)
    {
        heap[++heap_size] = node;
        pos[node] = heap_size;
        percolate(heap_size);
    }
    else
        percolate(pos[node]);
}

void removeTop()
{
    heap[1] = heap[heap_size];
    pos[heap[1]] = 1;
    --heap_size;
    if (heap_size <= 1) return;
    sift(1);
}

inline int heapSize()
{
    return heap_size;
}

void Dijkstra()
{
    int i, size;
    for (i=2; i<=N; ++i)
        d[i] = INF;

    int node = 1;
    insert(node);

    while (heapSize() > 0)
    {
        node = heap[1];
        removeTop();
        size = G[node].size();
        for (i=0; i<size; ++i)
        {
            int adj = G[node][i];
            if (d[node] + cost[node][i] < d[adj])
            {
                d[adj] = d[node] + cost[node][i];
                insert(adj);
            }
        }
    }
}

void afisare()
{
    ofstream out("dijkstra.out");
    for (int i=2; i<=N; ++i)
        out<<(d[i]==INF ? 0 : d[i])<<" ";
    out.close();
}

int main()
{
    citire();
    Dijkstra();
    afisare();
}