// C++ implementation of the approach
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// Function to print the required path
void printpath(vector<int>& parent, int vertex, int target)
{
if (vertex == 0) {
return;
}
printpath(parent, parent[vertex], target);
cout << vertex << (vertex == target ? "\n" : "--");
}
// Function to return the maximum weight
// in the widest path of the given graph
vector<int> widest_path_problem(vector<vector<pair<int, int> > >& Graph,
int src)
{
// To keep track of widest distance
vector<int> widest(Graph.size(), INT_MIN);
// To get the path at the end of the algorithm
vector<int> parent(Graph.size(), 0);
// Use of Minimum Priority Queue to keep track minimum
// widest distance vertex so far in the algorithm
priority_queue<pair<int, int>, vector<pair<int, int> >,
greater<pair<int, int> > >
container;
container.push(make_pair(0, src));
widest[src] = INT_MAX;
while (container.empty() == false) {
pair<int, int> temp = container.top();
int current_src = temp.second;
container.pop();
for (auto vertex : Graph[current_src]) {
// Finding the widest distance to the vertex
// using current_source vertex's widest distance
// and its widest distance so far
int distance = max(widest[vertex.second],
min(widest[current_src], vertex.first));
// Relaxation of edge and adding into Priority Queue
if (distance > widest[vertex.second]) {
// Updating bottle-neck distance
widest[vertex.second] = distance;
// To keep track of parent
parent[vertex.second] = current_src;
// Adding the relaxed edge in the priority queue
container.push(make_pair(distance, vertex.second));
}
}
}
//printpath(parent, target, target);
return widest;
}
// Driver code
int main()
{
// Graph representation
vector<vector<pair<int, int> > > graph;
int no_vertices = 4;
int n, m;
cin >> n >> m;
graph.assign(n + 1, vector<pair<int, int> >());
for (int i = 0; i < m; i++)
{
int a, b, w;
cin >> a >> b >> w;
graph[a].push_back(make_pair(w, b));
graph[b].push_back(make_pair(w, a));
}
for (int i = 2; i <= n; i++)
{
vector<int> t = widest_path_problem(graph, 1);
cout << t[i] << ' ';
}
cout << endl;
return 0;
}