#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
typedef int vert;
typedef int cost;
typedef pair<cost,vert> edge;
typedef vector<edge> edges;
typedef vector<edges> graph;
static const cost INF = 0x12345678; // large enough but INF+INF<2^31
static const vert START = 0;
static const vert GOAL = 1;
class WarTransportation { public:
int messenger(int n, vector <string> highways)
{
return solve( parse(n, highways) );
}
graph parse(int n, vector <string> highways)
{
graph G(n);
string hi = accumulate(highways.begin(), highways.end(), string());
for(int i=0; i<hi.size(); )
{
int k = hi.find(',', i);
if( k == string::npos ) k = hi.size();
int a, b, c;
stringstream(hi.substr(i,k-i)) >> a >> b >> c;
G[a-1].push_back( edge(c,b-1) );
i = k+1;
}
return G;
}
int solve( const graph& G )
{
// Suppose you reached the city "v", and found there the most critical load is broken.
// How long will it take a detour to the GOAL? It's ukai[v]!
vector<cost> ukai;
for(int v=0; v<G.size(); ++v)
ukai.push_back( ukaiDist(G,v) );
// Compute the least T such that:
// we get to the GOAL, making the worst case time <= T?
cost L=0, R=99999999;
if( !reachable(G, ukai, R) ) return -1;
if( reachable(G, ukai, L) ) return 0;
// We can when T=R, and cannot T=L.
// That is, T in (L, R]. Now let's binary-search!
while( R-L>1 )
(reachable(G, ukai, (L+R)/2) ? R : L) = (L+R)/2;
return R;
}
cost ukaiDist( const graph& G, vert v )
{
if( v == GOAL ) return 0;
if( G[v].size() == 0 ) return INF;
cost worst = 0;
for(int f=0; f<G[v].size(); ++f) // f : broken road
{
priority_queue< edge, vector<edge>, greater<edge> > Q;
set<vert> V;
V.insert(v);
for(int i=0; i<G[v].size(); ++i) // push all loads from v, except f
if( i != f )
Q.push( G[v][i] );
worst = max( worst, dijkstra(G,Q,V) ); // start dijkstraing
}
return worst;
}
bool reachable( const graph& G, const vector<cost>& ukai, cost ukaiLimit )
{
priority_queue< edge, vector<edge>, greater<edge> > Q;
set<vert> V;
Q.push( edge(0,START) );
return dijkstra(G, Q, V, ukai, ukaiLimit) != INF;
}
cost dijkstra( const graph& G,
priority_queue< edge, vector<edge>, greater<edge> >& Q, set<vert>& V,
const vector<cost>& ukai=vector<cost>(), cost ukaiLimit=-1
) {
while( !Q.empty() )
{
// pop
cost c = Q.top().first;
vert v = Q.top().second;
Q.pop();
// check
if( V.count(v) || (ukaiLimit>=0 && c+ukai[v]>ukaiLimit) )
continue;
if( v == GOAL )
return c;
V.insert(v);
// next
for(int i=0; i<G[v].size(); ++i)
if( !V.count(G[v][i].second) )
Q.push( edge(c+G[v][i].first, G[v][i].second) );
}
return INF;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, WarTransportation().messenger(n, highways));}
int main(){
CASE(0)
int n = 3;
string highways_[] = {"1 2 1,1 3 2,3 2 3"};
vector <string> highways(highways_, highways_+sizeof(highways_)/sizeof(*highways_));
int _ = 5;
END
CASE(1)
int n = 8;
string highways_[] = {"1 3 1,1 4 1,3 5 1,4 5 1,5 6 1,6 7 1,6 8 1,7 2 1,",
"8 2 1"};
vector <string> highways(highways_, highways_+sizeof(highways_)/sizeof(*highways_));
int _ = -1;
END
CASE(2)
int n = 4;
string highways_[] = {"1 3 1,1 3 2,3 2 1,1 4 1,4 2 1"};
vector <string> highways(highways_, highways_+sizeof(highways_)/sizeof(*highways_));
int _ = -1;
END
CASE(3)
int n = 4;
string highways_[] = {"1 3 1,3 2 1,1 4 1,4 2 1,3 4 1"};
vector <string> highways(highways_, highways_+sizeof(highways_)/sizeof(*highways_));
int _ = 3;
END
CASE(4)
int n = 20;
string highways_[] = {"1 13 3,13 4 7,4 3 4,3 10 8,10 18 9,18 12 6,12 2 3,",
"1 17 6,17 13 6,13 9 4,9 10 8,10 7 2,7 5 5,5 19 9,1",
"9 14 6,14 16 9,16 18 7,18 15 5,15 20 3,20 12 9,12 ",
"8 4,8 11 3,11 4 1,4 3 7,3 2 3,20 10 2,1 18 2,16 19",
" 9,4 15 9,13 15 6"};
vector <string> highways(highways_, highways_+sizeof(highways_)/sizeof(*highways_));
int _ = 23;
END
CASE(5)
int n = 30;
string highways_[] = {
"11 22 752,9 28 573,8 20 549,2 29 96,12 25 835,11 2", "3 443,28 20 59,5 16 223,29 24 382,14 6 436,5 21 47", "7,28 1 290,20 23 567,6 26 347,14 8 436,23 7 585,22", " 14 829,19 8 897,18 7 161,29 22 446,6 3 47,6 11 11", "9,23 13 357,15 2 539,30 27 246,20 26 364,11 13 518", ",20 29 360,10 9 140,9 19 178,24 5 75,4 9 465,22 4 ", "271,21 25 632,25 16 705,23 19 777,15 11 668,25 6 9", "11,26 21 940,27 12 114,23 29 775,15 22 907,10 15 1", "86,25 21 727,26 7 324,15 21 251,20 7 369,29 9 5,5 ", "4 780,10 23 774,13 15 65,2 8 938,9 3 150,6 9 109,4", " 22 649,24 13 274,14 3 403,12 19 66,3 13 798,7 20 ", "912,24 14 751,25 27 575,14 20 580,2 5 110,24 7 215", ",1 5 194,3 2 786,2 19 716,22 24 331,9 21 375,15 9 ", "397,18 27 753,24 23 181,17 27 386,12 30 313,18 25 ", "155,19 24 162,11 7 533,13 2 307,20 21 100,14 24 52", "6,29 8 505,28 8 776,5 27 949,16 14 43,16 30 84,10 ", "1 323,12 18 590,8 15 357,12 6 185,20 8 328,26 4 83", ",5 10 67,1 11 582,9 23 610,16 1 246,6 4 679,22 21 ", "149,17 10 321,29 27 560,20 19 771,11 30 506,6 25 1", "83,1 23 948,23 17 125,26 5 912,15 23 470,30 10 293", ",4 18 313,11 19 261,16 29 259,19 5 408,18 12 960,2", "4 3 743,17 3 4,30 17 347,11 2 648,16 8 868,12 10 6", "50,21 14 425,5 28 947,10 13 578,14 15 681,5 2 656,", "16 12 447,26 27 915,16 10 477,8 25 994,20 10 582,9", " 7 420,10 26 389,20 22 360,26 10 321,28 19 922,23 ", "20 393,13 14 447,29 15 33,30 1 811,2 28 597,13 8 5", "9,18 29 437,23 2 101,30 12 999,1 27 701,19 28 534,", "23 21 518,3 11 589,18 14 662,5 14 455,16 15 230,2 ", "17 633,19 13 242,10 18 404,10 4 731,15 6 221,25 15", " 747,3 23 465,24 9 569,12 11 645,5 24 748,23 26 44", "4,30 21 451,29 17 141,25 3 292,26 6 400,18 8 497,2", "4 19 901,17 5 49,21 12 141,30 18 7,20 18 271,13 3 ", "17,29 4 952,2 13 903,1 24 558,25 1 125,14 13 914,1", "4 12 385,1 3 40,30 8 704,18 5 901,19 10 822,22 27 ", "938,5 18 808,5 29 1,10 8 791,2 7 920,12 5 359,5 9 ", "744,1 25 819,6 30 262,24 6 7,12 7 870,17 25 932,28", " 18 771,23 16 699,26 24 834,27 20 824,30 23 95,22 ", "5 553,26 29 150,25 4 70,4 20 501,9 16 291,2 30 40,", "19 18 602,19 3 108,29 11 827,19 22 702,26 11 238,2", "8 22 392,22 10 496,13 25 160,12 24 700,22 29 654,9", " 2 701,28 7 946,21 5 223,7 22 902,12 15 43,21 8 67", "8,28 27 946,7 15 603,15 8 114,25 10 234,19 4 128,2", "4 8 990,11 12 554,23 9 646,10 24 755,8 16 857,23 1", " 806,15 13 929,21 11 601,19 30 245,17 21 474,27 25", " 638,11 21 411,4 26 895,13 24 599,12 13 226,30 22 ", "104,30 24 53,29 10 69,29 30 263,28 6 349,6 16 982,", "4 6 273,1 30 533,29 21 443,7 3 867,17 11 756,1 7 6", "87,29 2 799,5 22 42,16 20 708,25 11 476,23 8 186,2", "3 3 820,23 18 226,21 9 429,17 26 201,25 26 79,12 2", " 671,23 14 698,10 30 92,3 25 380,14 30 420"};
vector <string> highways(highways_, highways_+sizeof(highways_)/sizeof(*highways_));
int _ = 799;
END
/*
CASE(6)
int n = ;
string highways_[] = ;
vector <string> highways(highways_, highways_+sizeof(highways_)/sizeof(*highways_));
int _ = ;
END
*/
}
// END CUT HERE