#include "dreaming.h"
#include<vector>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
///Diameter of a tree
///Forest
///Determine the minimum longest distance after add N-M-1 new edges to the graph in an optimal way
bool byGreater(int a,int b)
{
return a>b;
}
struct edge
{
int from,to;
int w;
};
vector<edge> adjList[100005];
int far[100005]; //Stores the minimum longest distance for each tree
int color[100005];
int d[2][100005];
queue<int> Q;
int bfs(int s,int op,int c) ///Gets the distance to all nodes in its tree and return the farthest node
{
color[s]=c;
d[op][s]=0;
Q.push(s);
int farthest_node=s;
int maximum=0;
while(Q.size()){
int u=Q.front();Q.pop();
for(edge e: adjList[u]){
int v=e.to;
if(color[v]!=c){
color[v]=c;
d[op][v]=d[op][u]+e.w;
if(d[op][v]>maximum){
maximum=d[op][v];
farthest_node=v;
}
Q.push(v);
}
}
}
return farthest_node;
}
int getOptimumDistance(int s,int c) ///Returns the minimum longest distance in a tree
{
color[s]=c;
int minimumD=1000000000;
Q.push(s);
while(Q.size()){
int u=Q.front();Q.pop();
if(max(d[0][u],d[1][u])<minimumD){
minimumD=max(d[0][u],d[1][u]);
}
for(edge e: adjList[u]){
int v=e.to;
if(color[v]!=c){
color[v]=c;
Q.push(v);
}
}
}
return minimumD;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i=0;i<M;i++){ //Creates the graph
edge e={A[i],B[i],T[i]};
adjList[e.from].push_back(e);
swap(e.from,e.to);
adjList[e.from].push_back(e);
}
int answer=0;
int max_diameter=0;
int c=1;
int trees=0;
for(int u=0;u<N;u++){
if(color[u]!=0) continue;
int a=bfs(u,1,c++);
int b=bfs(a,0,c++);
bfs(b,1,c++);
max_diameter=max(max_diameter,d[1][a]); //Obtains the diameter of tree rooted at u
far[trees++]=getOptimumDistance(u,c++);
}
sort(far,far+trees,byGreater);
if(trees==1){
answer=max_diameter;
}
else if(trees==2){
answer=max(max_diameter,far[0]+L+far[1]); //Path joining yourself with another tree
}
else{
answer=max(max_diameter,
max(far[0]+L+far[1],far[1]+L+L+far[2])); //Path joining yourself with another tree
//and joining other two trees whose path passes for you
}
return answer;
}
