#include <fstream>
#include <cstdlib>
#include <vector>


using namespace std;

const static int nmax = 50010;
const static int Infinit = 1 << 30;

vector < pair <int,int> > graf[nmax];
int costuri[nmax];
bool sel[nmax];
pair <int,int> heap[nmax];
int size_heap = 0;
int num_nodes , num_edges;


void up_heap(int nod)
{
    if (nod < 1) return;

    if (heap[nod].first < heap[nod/2].first)
    {
        swap(heap[nod],heap[nod/2]);
        up_heap(nod/2);
    }
}

void down_heap(int nod)
{
    pair <int , int> next;
    int next_node = -1;

    if (2*nod <= size_heap)
    {
        if (heap[2*nod].first <heap[nod].first)
        {
            next_node = 2 * nod;
        }
    }

    if (2 * nod + 1 <= size_heap)
    {
        if (next_node == -1)
        {
            if (heap[2*nod+1].first < heap[nod].first)
            {
                next_node = 2 *nod + 1;
            }
        }
        else
        {
            if (heap[2*nod+1].first < heap[2*nod].first)
            {
                next_node = 2*nod+1;
            }
            else
            {
                next_node = 2*nod;
            }
        }
    }

    if (next_node != -1)
    {
        swap(heap[next_node],heap[nod]);
        down_heap(next_node);
    }

}

void insert_heap(int value , int node)
{
    size_heap += 1;
    heap[size_heap].first = value;
    heap[size_heap].second = node;
    up_heap(size_heap);
}

void delete_top()
{
    swap(heap[1],heap[size_heap]);
    size_heap --;
    down_heap(1);
}

void Dijkstra(int nod)
{
    fill(costuri+1,costuri+1+num_nodes,Infinit);
    fill(heap+1,heap+1+num_nodes,make_pair(Infinit,0));
    fill(sel+1,sel+1+num_nodes,false);
    costuri[1] = 0;
    insert_heap(0,1);
    for (int i = 0;i<num_nodes;i++)
    {
        nod = heap[1].second;
        sel[nod] = true;
        delete_top();
        for (int j =0;j<graf[nod].size();j++)
        {
            int x = graf[nod][j].second;
            if ( costuri[x] > costuri[nod] + graf[nod][j].first && !sel[x])
            {
                costuri[x] = costuri[nod] + graf[nod][j].first;
                insert_heap(costuri[x] , x);
            }
        }
    }
}




int main()
{
    ifstream input("dijkstra.in");
    ofstream output("dijkstra.out");
    input >> num_nodes >> num_edges;
    for (int i =0;i<num_edges;i++)
    {
        int x , y , c;
        input >> x >> y >> c;
        graf[x].push_back(make_pair(c,y));
    }
    Dijkstra(1);

    for (int i = 2;i<=num_nodes;i++)
    {
        if (costuri[i] != Infinit)
        {
            output << costuri[i] << " ";
        }
        else
        {
            output << "0 ";
        }
    }
    return 0;
}