#include<bits/stdc++.h>

using namespace std;

#define sp cout<<"---------------------------------------------------"<<endl;

const int inf=0x3f3f3f3f;

class WarTransportation{

      public:

          int head[],nxt[],to[],w[],cnt;

          int d2[],d[],vis[],bad[];

          int head2[],nxt2[],to2[],w2[],cnt2;

          priority_queue<pair<int,int> >q;

          void add(int x,int y,int z){

              nxt[++cnt]=head[x];

              head[x]=cnt;

              to[cnt]=y;

              w[cnt]=z;

              nxt2[++cnt2]=head2[y];

              head2[y]=cnt2;

              to2[cnt2]=x;

              w2[cnt2]=z;

          }

          int ndij(int s,int N){

              memset(vis,,sizeof(vis));

              memset(d,0x3f,sizeof(d));

              d[s]=;

            q.push(make_pair(,s));

              while(!q.empty()){

                  int x=q.top().second;

                  q.pop();

                  if(vis[x])continue;

                  vis[x]=;

                  for(int i=head[x];i;i=nxt[i])

                  if(i!=N||x!=s){

                      int y=to[i];

                      if(d[x]+w[i]<d[y]){

                          d[y]=d[x]+w[i];

                          q.push(make_pair(-d[y],y));

                      }

                    }

              }

              return d[];

          }

          void getbad(int n){

              int i,j;

              memset(bad,,sizeof(bad));

              for(i=;i<=n;i++)

                if(i!=)

                  for(j=head[i];j;j=nxt[j])

                    bad[i]=max(bad[i],ndij(i,j));

          }

          int getans(){

              memset(vis,,sizeof(vis));

              memset(d2,0x3f,sizeof(d2));

              d2[]=;

            q.push(make_pair(,));

            while(!q.empty()){

                int x=q.top().second;

                q.pop();

                if(vis[x])continue;

                vis[x]=;

                for(int i=head2[x];i;i=nxt2[i]){

                  int y=to2[i];

                  if(max(bad[y],d2[x]+w2[i])<d2[y]){

                      d2[y]=max(bad[y],d2[x]+w2[i]);

                      q.push(make_pair(-d2[y],y));

                  }

                }

            }

            if(d2[]>=inf)return -;

            return d2[];

        }

          int messenger(int n,vector<string>highways){

              int x,y,z;char ch;

              stringstream buf(accumulate(highways.begin(),highways.end(),string()));

            do{

              buf>>x>>y>>z;

              add(x,y,z);

            }while(buf>>ch);

            getbad(n);

            return getans();

          }

};