#include <fstream>
#include <cstdlib>
#include <vector>
#define left_son (nod << 1)
#define right_son left_son + 1


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)
{
    int next = nod;
    if ( left_son <= size_heap && heap[left_son] > heap[next]) next = left_son;
    if ( right_son <= size_heap && heap[right_son] > heap[next]) next = right_son;
    if (next != nod)
    {
        swap(heap[nod] , heap[next]);
        down_heap(next);
    }
}

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;
}