记录

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdlib>
#include<iomanip>
#include<map>
#define int long long
#define db long double
#define lc(p) p<<1
#define rc(p) p<<1|1
#define pii pair<int,int>
#define up(i,l,r) for(int i=(l);i<=(r);i++)
#define down(i,l,r) for(int i=(l);i>=(r);--i)
#define p_b push_back
#define m_p make_pair
using namespace std;
int n,m;
struct edge{
    int v,w;
};
struct node{
    int dis,u;
    bool operator>(const node &b)const{return dis>b.dis;}
};
int arr[100007],vis[100007];
int dis[100007];
int into[100007];
int rd[100007];
vector<int> gg[100007];
priority_queue<node,vector<node>,greater<node> > q;
vector<edge> e[100007];
void dijkstra(int s){
    node p={0,s};
    up(i,1,n){
        dis[i]=arr[i]=0x3f3f3f3f;
    }
    arr[s]=dis[s]=into[s]=0;
    q.push(p);
    while(!q.empty()){
        int u=q.top().u;
        q.pop();
        if(vis[u])continue;
        vis[u]=true;
        for(auto ed:e[u]){
            int v=ed.v;
            int w=ed.w;
            if(arr[v]>arr[u]+w){
                arr[v]=arr[u]+w;
                if(!rd[v]){
                    dis[v]=max(arr[v],into[v]);
                    q.push({dis[v],v});
                }
            }
        }
        for(auto v:gg[u]){
            into[v]=max(into[v],dis[u]);
            dis[v]=max(arr[v],into[v]);
            rd[v]--;
            if(!rd[v]){
                
                q.push({dis[v],v});
            }
        }
    }
}
signed main(){
    
    cin>>n>>m;
    up(i,1,m){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back((edge){v,w});
    }
    up(i,1,n){
        int t;
        cin>>t;
        up(j,1,t){
            int v;
            cin>>v;
            gg[v].push_back(i);
            rd[i]++;
        }
    }
    dijkstra(1);
    cout<<dis[n];
}