#include <iostream>
	
#include <fstream>
	
using namespace std;
	
ifstream f("dijkstra.in");
	
ofstream g("dijkstra.out");
	
template <class T>
class priority_queue {
private:
    #define MAX_HEAP_SIZE 5 // 16 * 1024 16384
    int count_max_heap_size, heap_size;
    T* heap; // max heap

    #define father(node) (node >> 1)        // (node / 2)
    #define left_son(node) (node << 1)      // (node * 2)
    #define right_son(node) (node << 1 | 1) // (node * 2 + 1)

public:
    priority_queue() { // constructor
        count_max_heap_size = 1;
        heap_size = 0;
        heap = (T*) malloc(MAX_HEAP_SIZE * sizeof(T));
    }

private:
    void reallocating_heap_memory() {
        count_max_heap_size++;

        T* new_heap = (T*) realloc (heap, count_max_heap_size * MAX_HEAP_SIZE * sizeof(T));

        if (new_heap != NULL) {
            heap = new_heap;
        } else {
            free(heap);
            puts("Error (re)allocating memory for heap");
            exit(1);
        }
    }

    void swap(T &a, T &b) {
        T tmp;
        tmp = a;
        a = b;
        b = tmp;
    }

    void up(int node) { // percolate
        while (1 < node && heap[father(node)] < heap[node]) {
            swap(heap[father(node)], heap[node]);
            node = father(node);
        }
    }
    
    void down(int node) { // sift
        int son;
        
        do {
            son = 0; // assume that the node can't go lower

            // get the son with maximum value in heap
            if (left_son(node) <= heap_size) {
                son = left_son(node);
                
                if (right_son(node) <= heap_size && heap[left_son(node)] < heap[right_son(node)]) {
                    son = right_son(node);
                }
                
                if (heap[son] < heap[node] ) {  // check if the node can go lower
                    son = 0;
                }
            }

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

public:
    int size() { 
        return heap_size;
    }

    bool empty() {
        if (heap_size) {
            return false;
        }
        return true;
    }

    inline T top() { // peek
        if (heap_size)  {
           return heap[1];
        }

        try {
           throw 2;
        } catch (int e) {
           printf("An exception occurred. Exception Nr. %d. Call top without having elements in heap\n", e);
        }
 
        return heap[0]; // get rid of the warning
    }

    void push(T value) {
        heap_size++;
        if (heap_size >= count_max_heap_size * MAX_HEAP_SIZE - 1) {
            reallocating_heap_memory();
        }

        heap[heap_size] = value;
        up(heap_size);
    }

    void pop() {
        swap(heap[1], heap[heap_size]);
        heap_size--;
        down(1);
    }
}; 
	
const int maxn = 50001;
	
const int inf = 1 << 30;
	
int N,M,val[maxn];
	
struct graf
	
{
	
    int info,cost;
	
    graf* urm;
	
}*pt[maxn];

class info
{
public:
	int nod;
	friend bool operator<(info a, info b) {
		return val[a.nod] < val[b.nod];
	}
};
	
 
	
void InserareGraf(graf* &point,int val,int ct)
	
{
	
   graf* cap = new graf;
	
   cap->info = val;
	
   cap->cost = ct;
	
   cap->urm = point;
	
   point = cap;
	
}	
 
	
void dijkstra(int xp)
	
{
    priority_queue<info>heap;
    int u;	

    for(int i = 1 ; i <= N ; i++)
        val[i] = inf;
	
    val[xp] = 0;

    info x;
    x.nod = xp;
    heap.push(x);
	
    while(!heap.empty())
	
    {
        u = heap.top().nod;
        heap.pop();
 
        graf* cap = pt[u];
	
 
	
        while( cap != NULL )
	
        {
	
            int y = cap->info;
	
            int ct = cap->cost;
	
 
	
            if( val[y] > val[u] + ct )
	
            {
	
                val[y] = val[u] + ct;

	            x.nod = y;
                heap.push(x);	
            }
	
            cap = cap->urm;
        }
	
    }
	
}
	
int main()
{
   int a,b,c;
   f >> N >> M;
	
    for(int i=1 ; i <= N ; i++)
       pt[i] = NULL;
	
    for(int i=1 ; i <= M ; i++)
    {
       f>>a>>b>>c;
       InserareGraf(pt[a],b,c);
    }
    dijkstra(1);
	
    for(int i = 2 ; i <= N ; i++)
      if(val[i] == inf)
        g<<0<<' ';
      else
        g<<val[i]<<' ';
    
    return 0;
}