#include <fstream>

const int INFINITY = INT_MAX;
const int Max = 101;
 
using namespace std;
 
class Dijkstra{
    private:
        int Adj[Max][Max];
        int predecessor[Max], distance[Max];
        bool mark[Max];
        int noNodes, noEdges, startNode, cost;
    public:
        void readData (fstream &); 
        void initializeData ();
        int getClosestUnmarkedNode ();
        void calculateDistance ();
        void writeData (fstream &);
        void printPath (int, fstream &);
};
 
 
void Dijkstra::readData(fstream &in){
	int nodeA, nodeB;
	in >> noNodes >> noEdges;
	startNode = 1;
	for (int i = 1; i <= noEdges; ++i){
		in >> nodeA >> nodeB >> cost;
		Adj[nodeA][nodeB] =  cost;
	}
	in.close();
}
 
 
void Dijkstra::initializeData(){
    for (int i = 1; i <= noNodes; ++i){
        mark[i] = false;
        predecessor[i] = -1;
        distance[i] = INFINITY;
    }
    distance[startNode] = 0;
}
 
 
int Dijkstra::getClosestUnmarkedNode(){
    int minDistance = INFINITY;
    int closestUnmarkedNode;
	for (int i = 1; i <= noNodes; ++i){
        if ((!mark[i]) && ( minDistance >= distance[i])) {
            minDistance = distance[i];
            closestUnmarkedNode = i;
        }
    }
    return closestUnmarkedNode;
}
 
 
void Dijkstra::calculateDistance(){
    initializeData();
    int minDistance = INFINITY;
    int closestUnmarkedNode;
    int count = 0;
    while(count < noNodes) {
        closestUnmarkedNode = getClosestUnmarkedNode();
        mark[closestUnmarkedNode] = true;
        for (int i = 1; i <= noNodes; ++i){
            if ((!mark[i]) && (Adj[closestUnmarkedNode][i] > 0) ) {
                if (distance[i] > distance[closestUnmarkedNode] + Adj[closestUnmarkedNode][i]) {
					distance[i] = distance[closestUnmarkedNode] + Adj[closestUnmarkedNode][i];
					predecessor[i] = closestUnmarkedNode;
                }
            }
        }
        count++;
    }
}
 
 
//void Dijkstra::printPath(int node, fstream &out){
//    if(node == startNode)
//        out << node << "..";
//    else if(predecessor[node] == -1)
//        out << "No path from " << startNode << "to " << node << endl;
//    else {
//        printPath(predecessor[node], out);
//        out << node << "..";
//    }
//}
 
 
void Dijkstra::writeData(fstream &out){
    for (int i = 2; i <= noNodes; ++i){
        /*if(i == startNode)
            out << startNode << ".." << startNode;
        else
            printPath(i, out);*/
        out << distance[i] << " ";
    }
}
 
 
int main (int argc, char *argv[]){
	fstream in("graph.in", ios::in);
	fstream out("graph.out", ios::out);
    Dijkstra Graph;
    Graph.readData(in);
    Graph.calculateDistance();
	Graph.writeData(out);
    return 0;
}