/* 
 * File:   main.cpp
 * Author: tkt_051
 *
 * Created on 20. kesäkuuta 2013, 11:07
 */

#include <iostream>
#include <vector>
#include <limits.h>
#include <cstdio>

struct Item
{
	unsigned int node;
	unsigned int dist;
	
	bool operator<(Item const& i) const
	{
		return dist < i.dist;
	}
};

class Heap
{
public:
	unsigned int size;
	
private:
	Item heap[100000];
	unsigned int nodePos[100000];
	
	void swap(unsigned int a, unsigned int b)
	{
		std::swap(nodePos[heap[a].node], nodePos[heap[b].node]);
		std::swap(heap[a], heap[b]);
	}
	
	void heapify(unsigned int i)
	{
		unsigned int l = i * 2;
		unsigned int r = i * 2 + 1;
		
		unsigned int s = i;
		
		if(l <= size && heap[l] < heap[s])
		{
			s = l;
		}
		
		if(r <= size && heap[r] < heap[s])
		{
			s = r;
		}
		
		if(s != i)
		{
			swap(s, i);
			heapify(s);
		}
	}
	
	void shiftUp(unsigned int i)
	{
		unsigned int p = i / 2;
		
		if(p != 0)
		{
			if(heap[i] < heap[p])
			{
				swap(i, p);
				shiftUp(p);
			}
		}
	}
	
public:
	
	Heap()
	{
		size = 0;
	}
	
	void change(unsigned int node, unsigned int newValue)
	{
		if(nodePos[node] == 0)
		{
			add(node, newValue);
			return;
		}
		
		unsigned int oldValue = heap[nodePos[node]].dist;
		
		heap[nodePos[node]].dist = newValue;
		
		if(oldValue < newValue)
		{
			heapify(node);
		}
		else
		{
			shiftUp(node);
		}
	}
	
	void add(unsigned int node, unsigned int dist)
	{
		size++;
		heap[size].node = node;
		heap[size].dist = dist;
		nodePos[node] = size;
		
		shiftUp(size);
	}
	
	unsigned int get(unsigned int node)
	{
		if(nodePos[node] == 0) return UINT_MAX;
		
		return heap[nodePos[node]].dist;
	}
	
	Item const& top()
	{
		return heap[1];
	}
	
	void pop()
	{
		swap(1, size);
		size--;
		heapify(1);
	}
	
	bool empty()
	{
		return size == 0;
	}
};

struct Edge
{
	unsigned int to;
	unsigned int len;
};

typedef std::vector<Edge> EdgeList;

struct Node
{
	EdgeList edges;
};

typedef std::vector<Node> NodeList;
NodeList nodes;

unsigned int nodeCount, edgeCount;

void readInput()
{
	std::cin >> nodeCount >> edgeCount;
	nodes.resize(nodeCount);
	
	for(unsigned int i = 0; i < edgeCount; i++)
	{
		unsigned int from;
		Edge edge;
		
		std::cin >> from >> edge.to >> edge.len;
		
		from--;
		edge.to--;
		
		nodes[from].edges.push_back(edge);
	}
}

std::vector<unsigned int> dist;
void dijkstra()
{
	Heap heap;
	dist.resize(nodeCount, UINT_MAX);
	dist[0] = 0;
	
	for(EdgeList::iterator it = nodes[0].edges.begin(); it != nodes[0].edges.end(); it++)
	{
		if(heap.get(it->to) > it->len) heap.change(it->to, it->len);
	}
	
	while(!heap.empty())
	{
		Item i = heap.top();
		dist[i.node] = i.dist;
		heap.pop();
		
		for(EdgeList::iterator it = nodes[i.node].edges.begin(); it != nodes[i.node].edges.end(); it++)
		{
			if(dist[it->to] != UINT_MAX) continue;
			unsigned int len = i.dist + it->len;
			if(heap.get(it->to) > len) heap.change(it->to, len);
		}
	}
}

void print()
{
	for(unsigned int i = 1; i < nodeCount; i++)
	{
		std::cout << (" " + (i == 1)) << dist[i];
	}
	
	std::cout << std::endl;
}

int main()
{
	/*Heap heap;
	heap.add(1, 5);
	heap.add(2, 10);
	heap.add(3, 2);
	heap.add(4, 11);
	heap.add(5, 3);
	
	heap.change(4, 1);
	heap.change(3, 12);
	
	while(!heap.empty())
	{
		Item const& i = heap.top();
		
		std::cout << i.node << " " << i.dist << std::endl;
		heap.pop();
	}*/
	
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	readInput();
	dijkstra();
	print();
	
	return 0;
}