#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define mp make_pair
#define F first
#define S second
#define PI 3.1415926535897932384626
#define sz(x) ((int)(x).size())
#define vset(v, n, val) v.clear(); v.resize(n, val)

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vull> vvull;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef vector<vs> vvs;

const int INF = 1e9;

class Solution {
public:

    // adjacency matrix representation of graph
    vvi g;

    // d[i][j] => shortest path length b/w vertices i & j
    vvi d;

    // nxt[][] is used to retrieve the actual path
    // nxt[i][j] => vertex which is just next to vertex 'i' in the
    //              shortest path from i to j
    // vvi nxt;

    // it will be true if there is -ve weight cycle in the graph
    // bool neg_cycle;

    // #vertices
    int n;

    // function to retrive the shortest paths (if exist) betweeen each pair of vertices
    // ref: https://www.geeksforgeeks.org/finding-shortest-path-between-any-two-nodes-using-floyd-warshall-algorithm/
//     void retrieve_paths() {
//         for(int i = 0; i < n; i++) {
//             for(int j = 0; j < n; j++) {
//                 cout << "For " << i << " to " << j << ": \n";
//                 // no shortest path exist if i and j part of -ve wt cycle
//                 if(d[i][j] == -INF) {
//                     cout << "No shortest path exists\n\n";
//                     continue;
//                 }

//                 // if path exist retrieve it
//                 int x = i, y = j;
//                 cout << x;
//                 if(x == y) {
//                     cout << "\n\n";
//                     continue;
//                 }

//                 cout << " -> ";

//                 while(x != y) {
//                     x = nxt[x][y];
//                     cout << x;
//                     if(x != y) cout << " -> ";
//                 }

//                 cout << "\n\n";
//             }
//         }
//     }

    // If required use long long instead of int data type,
    // 0-based indexing of vertices is used
    void floyd_warshall() {
        // initialisation of d[][] and nxt[][] arrays
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i == j) d[i][j] = 0;
                else {
                    if(g[i][j] == INF) d[i][j] = INF;
                    else d[i][j] = g[i][j];
                }
            }
        }

        // running main logic of the algorithm
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                for(int k = 0; k < n; k++) {
                    if(d[i][k] == INF or d[k][j] == INF) continue;
                    if(d[i][k] + d[k][j] < d[i][j]) {
                        d[i][j] = d[i][k] + d[k][j];
                    }
                }
            }
        }

//         neg_cycle = 0;

//         // to check if there is -ve weight cycle in the graph,
//         // therefore if d[i][j] == -INF, then pairs [i][j] don't have a shortest path between them
//         // ref: https://cp-algorithms.com/graph/finding-negative-cycle-in-graph.html
//         for(int i = 0; i < n; i++) {
//             for(int j = 0; j < n; j++) {
//                 for(int k = 0; k < n; k++) {
//                     if(d[i][k] < INF and d[k][k] < 0 and d[k][j] < INF) {
//                         d[i][j] = -INF;
//                         neg_cycle = 1;
//                     }
//                 }
//             }
//         }

//         retrieve_paths();
    }

    int findTheCity(int cities, vector<vector<int>>& edges, int distanceThreshold) {
        n = cities;

        g.clear();
        g.resize(n, vi(n, INF));

        d.clear();
        d.resize(n, vi(n));

        for(int i = 0; i < sz(edges); i++) {
            int u = edges[i][0], v = edges[i][1], wt = edges[i][2];
            g[u][v] = wt;
            g[v][u] = wt;
        }

        floyd_warshall();

        int res = -1, mn = INF;

        for(int i = 0; i < n; i++) {
            int cnt = 0;

            for(int j = 0; j < n; j++) {
                if(i == j) continue;
                if(d[i][j] <= distanceThreshold) cnt += 1;
            }

            if(cnt <= mn) {
                res = i;
                mn = cnt;
            }
        }

        return res;
    }
};