Untitled

#include <bits/stdc++.h>
using namespace std;
const int N = 5;

double minCostMST(vector<vector<int>>& graph, vector<bool>& visited) {
    vector<int> key(N, numeric_limits<int>::max());  // Initialize with max instead of min
    key[0] = 0;
    double minCost = 0;
    for (int cnt = 0; cnt < N - 1; ++cnt) {
        int u = -1;
        for (int v = 0; v < N; ++v) {
            if (!visited[v] && (u == -1 || key[v] < key[u])) {
                u = v;
            }
        }
        visited[u] = true;
        minCost += key[u];
        for (int v = 0; v < N; v++) {
            if (!visited[v] && graph[u][v] < key[v]) {
                key[v] = graph[u][v];
            }
        }
    }
    return minCost;
}

vector<int> tspMST(vector<vector<int>>& graph) {
    vector<bool> visited(N, false);
    double minCost = minCostMST(graph, visited);
    vector<int> tour;
    tour.push_back(0);
    int currentCity = 0;

    for (int i = 1; i < N; i++) {
        int nextCity = -1;
        double minEdge = numeric_limits<int>::max();  // Initialize with max instead of min
        for (int j = 0; j < N; j++) {
            if (!visited[j] && graph[currentCity][j] < minEdge) {
                minEdge = graph[currentCity][j];
                nextCity = j;
            }
        }
        if (nextCity != -1) {
            tour.push_back(nextCity);
            visited[nextCity] = true;
            currentCity = nextCity;
        }
    }
    tour.push_back(0);
    return tour;
}

int main() {
    vector<vector<int>> graph(N, vector<int>(N, 0));
    for (int i = 0; i < N; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u][v] = w;
        graph[v][u] = w;
    }

    vector<int> tour = tspMST(graph);

    for (int city : tour) {
        cout << city << " ";
    }
    cout << endl;
}