<p>You are given a positive integer <code>n</code> representing <code>n</code> cities numbered from <code>1</code> to <code>n</code>. You are also given a <strong>2D</strong> array <code>roads</code> where <code>roads[i] = [a<sub>i</sub>, b<sub>i</sub>, distance<sub>i</sub>]</code> indicates that there is a <strong>bidirectional </strong>road between cities <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code> with a distance equal to <code>distance<sub>i</sub></code>. The cities graph is not necessarily connected.</p>

<p>The <strong>score</strong> of a path between two cities is defined as the <strong>minimum </strong>distance of a road in this path.</p>

<p>Return <em>the <strong>minimum </strong>possible score of a path between cities </em><code>1</code><em> and </em><code>n</code>.</p>

<p><strong>Note</strong>:</p>

<ul>
	<li>A path is a sequence of roads between two cities.</li>
	<li>It is allowed for a path to contain the same road <strong>multiple</strong> times, and you can visit cities <code>1</code> and <code>n</code> multiple times along the path.</li>
	<li>The test cases are generated such that there is <strong>at least</strong> one path between <code>1</code> and <code>n</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/10/12/graph11.png" style="width: 190px; height: 231px;" />
<pre>
<strong>Input:</strong> n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
<strong>Output:</strong> 5
<strong>Explanation:</strong> The path from city 1 to 4 with the minimum score is: 1 -&gt; 2 -&gt; 4. The score of this path is min(9,5) = 5.
It can be shown that no other path has less score.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/10/12/graph22.png" style="width: 190px; height: 231px;" />
<pre>
<strong>Input:</strong> n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> The path from city 1 to 4 with the minimum score is: 1 -&gt; 2 -&gt; 1 -&gt; 3 -&gt; 4. The score of this path is min(2,2,4,7) = 2.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= roads.length &lt;= 10<sup>5</sup></code></li>
	<li><code>roads[i].length == 3</code></li>
	<li><code>1 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n</code></li>
	<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>
	<li><code>1 &lt;= distance<sub>i</sub> &lt;= 10<sup>4</sup></code></li>
	<li>There are no repeated edges.</li>
	<li>There is at least one path between <code>1</code> and <code>n</code>.</li>
</ul>

class DSU{
    public:
    vector<int>rank,parent;
    DSU(int n){
       rank.resize(n+1,0);
       parent.resize(n+1);
       for(int i=1;i<=n;i++)parent[i]=i;
    }
    int findpar(int u){
          if(parent[u]==u)return u;
          return parent[u]=findpar(parent[u]);
    }
    void ubrank(int u,int v){
        int up=findpar(u);
        int vp=findpar(v);
        if(up==vp)return;
        if(rank[up]<rank[vp]){
            parent[up]=vp;
        }else if(rank[up]>rank[vp]){
            parent[vp]=up;
        }else{
            parent[vp]=up;
            rank[up]++;
        }
        return;
    }
};

class Solution {
public:
static bool comp(const vector<int>&a,const vector<int>&b){
    return a[2]<b[2];
}
    int minScore(int n, vector<vector<int>>& roads) {
        sort(roads.begin(),roads.end(),comp);
        // return roads[0][2];
        DSU ds(n);
        for(auto t:roads){
            ds.ubrank(t[0],t[1]);
        }
        for (auto& t : roads) {
            if (ds.findpar(1) == ds.findpar(t[0]) || ds.findpar(1) == ds.findpar(t[1])) {
                return t[2];
            }
        }
        return 0;

    }
};


// class Solution {
// public:
//     int minScore(int n, vector<vector<int>>& roads) 
//     {
//         // Storing graph in a adjacency list
//         vector<int> adj[n+1];
//         for(int i=0;i<roads.size();i++)
//         {
//             adj[roads[i][0]].push_back(roads[i][1]);
//             adj[roads[i][1]].push_back(roads[i][0]);
//         }

//         // making a visited array for keep tracking of all the cities (we have visited or not)
//         // n = number of cities
//         vector<bool> vis(n+1,false);
//         vis[1] = true;                                  // mark source node as a visited city
        
//         // BFS
//         queue<int> q;
//         q.push(1);

//         while(!q.empty())
//         {
//             int node = q.front();
//             q.pop();

//             for(auto &it : adj[node])
//             {
//                 if(!vis[it])
//                 {
//                     vis[it] = true;
//                     q.push(it);
//                 }
//             }
//         }


//         // Computing minimum distance from city 1 to n
//         int ans = INT_MAX;
//         for(int i=0;i<roads.size();i++)
//         {
//             // minimum possible score out of all available paths
//             // if src and dest both are visited cities then try to make this our ans
//             if(vis[roads[i][0]] && vis[roads[i][1]])
//             {
//                 ans = min(ans,roads[i][2]);
//             }
//         }

//         return ans;
//     }
// };
118196