#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]; bool seen[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)
{
    int son;
    do
    {
        son = 0;
        int left_son = leftSon(node);
        int right_son = rightSon(node);
        if (left_son <= heap_size)
        {
            son = left_son;
            if (right_son<=heap_size && heap[right_son]<heap[left_son])
                son = right_son;
        }

        if (son != 0)
        {
            swap(heap[node], heap[son]);
            swap(pos[heap[node]], pos[heap[son]]);
            node = son;
        }
    }
    while (son != 0);
}

void percolate(int node)
{
    int val = heap[node];
    while (val<heap[father(node)] && node>1)
    {
        heap[node] = heap[father(node)];
        pos[heap[father(node)]] = pos[heap[node]];
        node = father(node);
    }
    heap[node] = val;
    pos[heap[node]] = node;
}

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

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

void updatePosition(const int &node)
{
    if (node>1 && heap[node]<heap[father(node)])
        percolate(node);
    else sift(node);
}

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];
        seen[node] = 1;
        size = G[node].size();
        for (i=0; i<size; ++i)
        {
            int adj = G[node][i];
            bool changed = 0;
            if (d[node] + cost[node][i] < d[adj])
            {
                changed = 1;
                d[adj] = d[node] + cost[node][i];
            }
            if (seen[adj] == 0) insert(adj);
            else if (changed == 1)
                updatePosition(adj);
        }
        removeTop();
    }
}

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

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