class WarTransportation {
public:
int messenger(int, vector <string>);
};
const int maxn=100,inf=1<<29;int n;
struct edge
{
int s,t,c,dcost;bool e;
edge(int _s,int _t,int _c):s(_s),t(_t),c(_c),e(true){}
};
vector<edge> E[maxn];
typedef vector<edge>::iterator it;
void add_edge(vector<edge> E[maxn],int s,int t,int c)
{E[s].push_back(edge(s,t,c));}
void spfa(vector<edge> E[maxn],it d)
{
d->e=false;int dist[maxn];rep(i,n) dist[i]=inf;
bool inq[maxn]={0};inq[1]=true;dist[1]=0;
queue<int> Q;Q.push(1);
while(Q.size())
{
int t=Q.front();Q.pop();inq[t]=false;int cost=dist[t];
for(it i=E[t].begin();i!=E[t].end();i++)if(i->e)
{
int ncost=cost+i->c;
if(ncost<dist[i->t])
{
dist[i->t]=ncost;
if(!inq[i->t]) Q.push(i->t),inq[i->t]=true;
}
}
}
d->dcost=dist[d->t];d->e=true;
}
int WarTransportation::messenger(int _n, vector <string> h) {
n=_n;
string A;for(int i=0;i<h.size();i++) A+=h[i];
istringstream in(A);int s,t,c;char tmp;
do
{
in>>s>>t>>c;s–;t–;
add_edge(E,t,s,c);
}while(in>>tmp);
rep(i,n)
{
for(it e=E[i].begin();e!=E[i].end();e++)
spfa(E,e),cout<<e->t+1<<"->"<<e->s+1<<":"<<e->dcost<<endl;
}
int dist[maxn];rep(i,n) dist[i]=inf;
bool inq[maxn]={0};inq[1]=true;dist[1]=0;
queue<int> Q;Q.push(1);
while(Q.size())
{
int t=Q.front();Q.pop();inq[t]=false;int cost=dist[t];
for(it i=E[t].begin();i!=E[t].end();i++)
{
int ncost=max(cost+i->c,i->dcost);
if(ncost<dist[i->t])
{
dist[i->t]=ncost;
if(!inq[i->t]) Q.push(i->t),inq[i->t]=true;
}
}
}
if(dist[0]==inf) return -1;
return dist[0];
}