#include <iostream>
#include <fstream>
#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>





#ifndef __GRAPH__
#define __GRAPH__

#include<unordered_set>
#include<unordered_map>
#include<list>
#include<vector>
#include<utility> //pair
using namespace std;

template<typename WeightType = unsigned int>
class Graph {

	private:
		//directed flag (the graph is directed if set to true)
		const bool is_directed;
		//weighted flag (the graph is edge-weighted if set to true)
		const bool is_weighted;

		//number of edges (or arcs, if directed)
		unsigned int m;

		//out-neighborhood
		unordered_map< unsigned int, unordered_map<unsigned int, WeightType> > Out;
		//in-neighborhood (unused if undirected)
		unordered_map< unsigned int, unordered_map<unsigned int, WeightType> > In;

		//set of all vertices
		unordered_set<unsigned int> vertices;

		//garbage: removed vertices
		list<unsigned int> dead_vertices;
		//generation of a default ID
		unsigned int gen_id(void);

		void do_DFS_helper(unsigned int node,
			  			   unsigned int distance,
						   vector< pair<unsigned int, unsigned int> >& result,
	                       unordered_set<unsigned int>& visited) const;

	public:
		Graph(bool,bool); //construction of a undirected/directed unweighted/weighted null graph
		Graph(); //construction of a null undirected unweighted graph

		//graph information
		inline unsigned int order(void) const {return vertices.size(); } //number of nodes
		inline unsigned int size(void) const { return m; } //number of edges
		inline bool directed(void) const { return is_directed; }
		inline bool weighted(void) const { return is_weighted; }

		//vertex information
		list<unsigned int> vertex_list(void) const; //enumerate all vertices
		bool node_exists(unsigned int v) const;
		int degree(unsigned int) const; //total degree of a node (-1 if node does not exist)
		int out_degree(unsigned int) const;
		int in_degree(unsigned int) const;
		list<unsigned int> neighbours(unsigned int) const; //enumerate all (out-)neighbours of a node
		list<unsigned int> in_neighbours(unsigned int) const;

		//edge information
		list< pair<unsigned int, unsigned int> > edges(void) const; //enumerate all arcs
		WeightType weight(unsigned int,unsigned int) const; //arc weight (1 if undirected, undefined if arc does not exist)
		bool adjacent(unsigned int, unsigned int) const;

		//dynamic operations
		bool add_edge(unsigned int,unsigned int, WeightType = 1); //adds a new edge, if it is not already present
		bool remove_edge(unsigned int, unsigned int); //removes an edge, if it is already present

		int add_node(int = -1); //inserts a new isolated vertex, and outputs its ID
		bool remove_node(unsigned int); //removes a node, being given its ID

		int contract(unsigned int, unsigned int, int = -1); //contract two adjacent vertices, and outputs the ID of the resulting node


		/**
		 * Start a depth-first search from startNode and return a vector of (node, distance) pairs.
		 * Note: The graph MUST be unweighted (otherwise, DFS doesn't make sense).
		*/
		vector<pair<unsigned int, unsigned int>> do_DFS(unsigned int startNode) const;

		/**
		 * Start a breadth-first search from startNode and return a vector of (node, distance) pairs,
		 * which will be sorted increasingly by distance.
		 * Note: The graph MUST be unweighted (otherwise, BFS doesn't make sense).
		*/
		vector<pair<unsigned int, unsigned int>> do_BFS(unsigned int startNode) const;

		/**
		 * Apply Dijkstra's algorithm from startNode and return a mapping from 'node' to distance(startNode, node).
		*/
		unordered_map<unsigned int, WeightType> do_Dijkstra(unsigned int startNode) const;

		/**
		 * Return the diameter of the graph (the longest shortest path between two nodes).
		 * -1 will be returned for a graph that is not connected.
		 * Note: The graph MUST be unweighted (otherwise, this implementation doesn't apply).
		*/
		unsigned int get_diameter_unweighted() const;
};


#include <iostream>
#include <stdio.h>

#define pv(x) std::cout<<#x<<" = "<<(x)<<"; ";std::cout.flush()
#define pn std::cout<<std::endl

#define killProgram(msg, ...) \
    do { fprintf(stderr, msg "\n", ##__VA_ARGS__); exit(-1); } while (0)




#include <assert.h>
#include <algorithm>
#include <limits>
#include <set>
#include <stack>


#define AssertNodeExistance(node) \
    do { \
        if (this->vertices.count(node) == 0) \
            killProgram("%s (Line %i)  --->  Node %i doesn't exist!", __PRETTY_FUNCTION__, __LINE__, (node)); \
    } while (0)


template<typename WeightType>
Graph<WeightType>::Graph(bool d, bool w): is_directed(d), is_weighted(w), m(0) {}

template<typename WeightType>
Graph<WeightType>::Graph(): Graph<WeightType>::Graph(0,0) {}

template<typename WeightType>
list<unsigned int> Graph<WeightType>::vertex_list(void) const {
	list<unsigned int> _all;

	for (unsigned int v: vertices) {
		_all.push_back(v);
	}

	_all.sort();

	return _all;
}

template<typename WeightType>
bool Graph<WeightType>::node_exists(unsigned int v) const {
	return (vertices.find(v) != vertices.end());
}

template<typename WeightType>
int Graph<WeightType>::degree(unsigned int v) const {
	if (vertices.find(v) == vertices.end()) {
		return -1;
	}

	if (directed()) {
		return in_degree(v) + out_degree(v);
	}
	else {
		return out_degree(v);
	}
}

template<typename WeightType>
int Graph<WeightType>::out_degree(unsigned int v) const{
	if (vertices.find(v) == vertices.end()) return -1;
	else if (Out.find(v) == Out.end()) return 0;
	else return (Out.find(v)->second).size();
}

template<typename WeightType>
int Graph<WeightType>::in_degree(unsigned int v) const{
	if (!directed()) return out_degree(v);
	else if (vertices.find(v) == vertices.end()) return -1;
	else if (In.find(v) == In.end()) return 0;
	else return (In.find(v)->second).size();
}

template<typename WeightType>
list<unsigned int> Graph<WeightType>::neighbours(unsigned int v) const {
	AssertNodeExistance(v);

	list<unsigned int> out_list;
	if (Out.find(v) != Out.end()) {
	 	for (auto e : Out.find(v)->second) {
	  		out_list.push_back(e.first);
		}
	}

	return out_list;
}

template<typename WeightType>
list<unsigned int> Graph<WeightType>::in_neighbours(unsigned int v) const {
	AssertNodeExistance(v);

	list<unsigned int> in_list;
	if (In.find(v) != In.end()) {
		for (auto e : In.find(v)->second) {
	  		in_list.push_back(e.first);
		}
	}

	return in_list;
}


template<typename WeightType>
list< pair<unsigned int, unsigned int> > Graph<WeightType>::edges(void) const {
	list< pair<unsigned int,unsigned int> > _all;

	for (auto adj_list: Out){
		unsigned int v = adj_list.first; //non-isolated vertices
		for (auto e: adj_list.second){ //pairs (neighbour,weight)
			unsigned int u = e.first;
			if (directed() || v < u) {
				_all.push_back(pair<unsigned int, unsigned int>(v,u));
			}
		}
	}

	_all.sort();

	return _all;
}

template<typename WeightType>
bool Graph<WeightType>::adjacent(unsigned int u, unsigned int v) const {
	AssertNodeExistance(u); AssertNodeExistance(v);

	if (Out.find(u) == Out.end()) {
		return 0;
	}

	auto adj_list = &(Out.find(u)->second);
	return ( adj_list->find(v) != adj_list->end() );
}

template<typename WeightType>
WeightType Graph<WeightType>::weight(unsigned int u,unsigned int v) const {
	if (!adjacent(u,v)) return (WeightType)-1;

	auto adj_list = &(Out.find(u)->second);
	return adj_list->find(v)->second;
}


template<typename WeightType>
bool Graph<WeightType>::add_edge(unsigned int u,unsigned int v, WeightType w){
	if (vertices.find(u) == vertices.end() || vertices.find(v) == vertices.end() || adjacent(u,v) || u == v) {
	 	return 0;
	}

	if (!weighted() && w != 1) {
		assert(0 && "Can't add a weight that's different from 1 to an unweighted graph!");
	}

	Out[u][v] = w; //creates key u if it is its first outgoing edge
	if (directed()) {
		// In[v][u] = w;
	}
	else {
		Out[v][u] = w;
	}

	m++;

	return 1;
}

template<typename WeightType>
bool Graph<WeightType>::remove_edge(unsigned int u, unsigned int v) {
	AssertNodeExistance(u); AssertNodeExistance(v);
	if (!adjacent(u,v)) { return 0; }

	Out[u].erase(v);
	if (Out[u].empty()) {
		Out.erase(u);
	}

	if (directed()) {
		In[v].erase(u);
	 	if (In[v].empty()) {
			In.erase(v);
		}
	}
	else {
	 	Out[v].erase(u);
	 	if (Out[v].empty()) {
			Out.erase(v);
		}
	}

	m--;

	return 1;
}

template<typename WeightType>
unsigned int Graph<WeightType>::gen_id(void) {
	if (dead_vertices.empty()) {
		return order();
	}

	unsigned int zombie = dead_vertices.front();
	dead_vertices.pop_front();
	return zombie;
}

template<typename WeightType>
int Graph<WeightType>::add_node(int v) {
	if (v < 0) {
		v = gen_id();
	}

	if (vertices.find(v) != vertices.end()) {
		return -1;
	}

	vertices.insert(v);
	return v;
}


template<typename WeightType>
bool Graph<WeightType>::remove_node(unsigned int v) {
	if (vertices.find(v) == vertices.end()) {
		return 0;
	}

	for (auto u : neighbours(v)) {
		remove_edge(v, u);
	}

	for (auto u: in_neighbours(v)) {
		remove_edge(u,v);
	}

	vertices.erase(v);
	dead_vertices.push_back(v);

	return 1;
}

template<typename WeightType>
int Graph<WeightType>::contract(unsigned int x, unsigned int y, int z) {
	AssertNodeExistance(x); AssertNodeExistance(y);
	if (z < 0) z = x;

	if (!adjacent(x,y)) return -1;
	if (z != (int)x && z != (int)y && vertices.find(z) != vertices.end()) return -1;

	list<unsigned int> out_x = neighbours(x), in_x = in_neighbours(x),
					   out_y = neighbours(y), in_y = in_neighbours(y);
	remove_node(x); remove_node(y);
	add_node(z);
	for (unsigned int v: out_x) add_edge(z,v);
	for (unsigned int v: out_y) add_edge(z,v);
	for (unsigned int u: in_x) add_edge(u,z);
	for (unsigned int u: in_y) add_edge(u,z);
	return z;
}


template<typename WeightType>
void Graph<WeightType>::do_DFS_helper(unsigned int node,
									  unsigned int distance,
									  vector< pair<unsigned int, unsigned int> >& result,
									  unordered_set<unsigned int>& visited) const {
	visited.insert(node);
	result.push_back({node, distance});

	if (Out.find(node) == Out.end()) {
		return;
	}

	for (auto p : Out.at(node)) {
		unsigned int nxt = p.first;
		if (visited.find(nxt) == visited.end()) {
			do_DFS_helper(nxt, distance + 1, result, visited);
		}
	}
}

template<typename WeightType>
vector< pair<unsigned int, unsigned int> > Graph<WeightType>::do_DFS(unsigned int startNode) const {
	assert(!weighted());
	AssertNodeExistance(startNode);

    vector< pair<unsigned int, unsigned int> > result;
	unordered_set<unsigned int> visited;
	do_DFS_helper(startNode, 0, result, visited);

	return result;
}

template<typename WeightType>
vector<pair<unsigned int, unsigned int>> Graph<WeightType>::do_BFS(unsigned int startNode) const {
	assert(!weighted());
	AssertNodeExistance(startNode);

    vector<pair<unsigned int, unsigned int>> pseudoQueue;
    unordered_set<unsigned int> visited;

    pseudoQueue.push_back({startNode, 0});
    visited.insert(startNode);
    int frontIndex = 0;
    while (frontIndex < (int)pseudoQueue.size()) {
        auto currPair = pseudoQueue[frontIndex++];
        unsigned int node = currPair.first;
        unsigned int dist = currPair.second;

		if (Out.find(node) == Out.end()) {
			continue;
		}

		for (auto p : Out.at(node)) {
			unsigned int nxt = p.first;
            if (visited.count(nxt) == 0) {
                visited.insert(nxt);
                pseudoQueue.push_back({nxt, dist + 1});
            }
        }
    }

    return pseudoQueue;
}

template<typename WeightType>
unordered_map<unsigned int, WeightType> Graph<WeightType>::do_Dijkstra(unsigned int startNode) const {
	AssertNodeExistance(startNode);
	vector<char> visited(order() + 1);
    vector<unsigned int> dist(order() + 1);
	set< pair<WeightType, unsigned int> > heap;

	for (unsigned int node : vertices) {
		dist[node] = (unsigned int)-1;
	}

	dist[startNode] = 0;
	heap.insert({0, startNode});
	while (heap.size()) {
		auto closestPair = *heap.begin();
		heap.erase(closestPair);
		unsigned int currDist = closestPair.first;
		unsigned int currNode = closestPair.second;

		visited[currNode] = 1;

		if (Out.find(currNode) == Out.end()) {
			continue;
		}

		for (auto nxtPair : Out.at(currNode)) {
			WeightType nxtWeight = nxtPair.second;
			unsigned int nxtNode = nxtPair.first;
			if (visited[nxtNode] == 0 && dist[nxtNode] > currDist + nxtWeight) {
				heap.erase({dist[nxtNode], nxtNode});
				dist[nxtNode] = currDist + nxtWeight;
				heap.insert({dist[nxtNode], nxtNode});
			}
		}
	}

    visited.clear();

	unordered_map<unsigned int, WeightType> distRet;
    for (unsigned int node = 1; node <= order(); ++node) {
        distRet[node] = dist[node];
    }

	return distRet;
}

template<typename WeightType>
unsigned int Graph<WeightType>::get_diameter_unweighted() const {
	assert(!weighted());
    assert(order() > 0);

    const list<unsigned int> allNodes = vertex_list();

    unsigned int diameter = 0;
    for (const unsigned int node : allNodes) {
        const vector<pair<unsigned int, unsigned int>> bfsResult = do_BFS(node);
        if (bfsResult.size() != allNodes.size()) {
            return 1<<31; // Graph is not connected. Infinite diameter.
        }

        unsigned int maxDistanceForCurrentNode = bfsResult[bfsResult.size() - 1].second;
        diameter = max(diameter, maxDistanceForCurrentNode);
    }

    return diameter;
}


#endif











using namespace std;


int main() {
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");

    unsigned int N, M;
    in >> N >> M;

    Graph<unsigned int> g(1, 1);
    for (unsigned int node = 1; node <= N; ++node) {
        g.add_node(node);
    }

    for (unsigned int i = 1; i <= M; ++i) {
        int x, y, c;
        in >> x >> y >> c;
        g.add_edge(x, y, c);
    }

    unordered_map<unsigned int, unsigned int> dist = g.do_Dijkstra(1);
    for (unsigned int node = 2; node <= N; ++node) {
        out << ((dist[node] != (unsigned int)-1) ? dist[node] : 0) << ' ';
    }
    out << '\n';

    in.close();out.close();
    return 0;
}