#include<bits/stdc++.h>
#define reg register
#define int long long
inline int read(){
    reg int x=0,k=1; reg char ch=getchar();
    while ('0'>ch||ch>'9') (ch=='-')&&(k=-1),ch=getchar();
    while ('0'<=ch&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*k;
}
inline bool cmin(reg int &x,reg int y){return x>y?x=y,1:0;}
const int N=4e5+10;
// int n,m,k,tot,a[N],ban[N],fail[N];
// int id[N],idx,dis[N],rt[N],vis[N];
// std::map<int,int> G[N],ch[N];
// struct tree{int ls,rs; std::pair<int,int> val;}t[N*20];
// std::priority_queue<std::pair<int,int>> pq;
// void modify(reg int &o,reg int pre,reg int l,reg int r,reg int x,reg std::pair<int,int> v){
//     t[o=++idx]=t[pre]; if (l==r) return t[o].val=v,void(); reg int mid=l+r>>1;
//     x<=mid?modify(t[o].ls,t[pre].ls,l,mid,x,v):modify(t[o].rs,t[pre].rs,mid+1,r,x,v);
// }
// int query(reg int o,reg int l,reg int r,reg int x){
//     if (!o) return 0; if (l==r) return t[o].val.first; reg int mid=l+r>>1;
//     return x<=mid?query(t[o].ls,l,mid,x):query(t[o].rs,mid+1,r,x);
// }
// void update(reg int &o,reg int l,reg int r,reg int d){
//     if (!o) return; 
//     if (l==r){
//         auto [v,w]=t[o].val; 
//         if (!ban[v]&&cmin(dis[v],d+w)) pq.push({-dis[v],v}); 
//         o=0; return;
//     }
//     reg int mid=l+r>>1; update(t[o].ls,l,mid,d),update(t[o].rs,mid+1,r,d); o=0;
// }
// inline void bfs(){
//     std::queue<int> q;
//     for (reg int i=1;i<=n;i++){
//         q.push(ch[0][i]);
//         for (auto [v,w]:G[i]) modify(rt[i],rt[i],1,n,v,{v,w});
//     }
//     while (!q.empty()){
//         reg int u=q.front(); q.pop(),ban[u]|=ban[fail[u]];
//         if (fail[u]){
//             t[rt[u]=++idx]=t[rt[fail[u]]];
//         }
//         for (auto [c,v]:ch[u]){
//             modify(rt[u],rt[u],1,n,c,{v,G[id[u]][c]});
//             if (fail[u]) fail[v]=query(rt[fail[u]],1,n,c); else fail[v]=c;
//             q.push(v);
//         } 
//     }
// }
signed main(){
    // freopen("compete.in","r",stdin),freopen("compete.out","w",stdout);
    return 0;
    // tot=n=read(),m=read(),k=read();
    // for (reg int i=1,u,v;i<=m;i++) u=read(),v=read(),G[u][v]=read();
    // for (reg int i=1;i<=n;i++) id[ch[0][i]=i]=i;
    // while (k--){ 
    //     reg int len=read(),p=0,c;
    //     for (;len--;p=ch[p][c]){
    //         c=read();
    //         if (!ch[p].count(c)) id[ch[p][c]=++tot]=c;
    //     }
    //     ban[p]=1;
    // }
    // memset(dis,0x3f,sizeof(dis)),bfs(); 
    // if (ban[1]) return puts("-1"),0; pq.push({dis[1]=0,1});
    // while (!pq.empty()){
    //     auto [d,u]=pq.top(); pq.pop();
    //     if (vis[u]) continue; if (id[u]==n) return printf("%lld\n",-d);
    //     vis[u]=1,update(rt[u],1,n,-d); 
    // }
    // puts("-1");
    return 0;
}