I was hoping that there's a greedy for the full solution since constraints seemed too big for dp. But looking at submissions from oj.uz there seems to be a dp solution. On greedy, i tried to always use the shop with highest money and failed.

    #include <bits/stdc++.h>
    #include "traffic.h"
    #define pb push_back
     
    using namespace std;
	
    vector<vector<int>> adj(1000000,vector<int>());
 
    map<pair<int,int>,int> m;
 
    int dp(int p,int c,int* P){
        if(m.find((pair<int,int>){p,c})!=m.end())return m[(pair<int,int>){p,c}];
        int ans = P[c];
        for(int v:adj[c]){
            if(v==p)continue;
            ans += dp(c,v,P);
        }
        m.insert({{p,c},ans});
        return ans;
	}
     
    int LocateCentre(int n,int p[],int s[],int d[]){
      for(int i=0;i<n-1;i++){
        adj.at(s[i]).pb(d[i]);
        adj.at(d[i]).pb(s[i]);
      }
      int ans = INT_MAX,index = -1;
      for(int i=0;i<n;i++){
          int local = INT_MIN;
          for(int v:adj[i])local = max(local,dp(i,v,p));
          if(local<ans){
              ans = local;
              index = i;
          }
      }
      return index;
    }

2010	Memory                       	93.19
2010	Cluedo                       	92.69
2009	Garage                       	91.55
2009	Poi                          	90.05
2006	Deciphering the Mayan Writing	80.62
2020	Connecting Supertrees        	77.93
2010	Traffic Congestion           	75.91
2019	Arranging Shoes              	74.47
2018	Combo                        	74.12
2009	Raisins                      	70.55
2007	Miners                       	68.31
2016	Detecting Molecules          	66.02
2013	Cave                         	64.39
2014	Gondola                      	64.26
2016	Paint by Number              	63.6
2011	Parrots                      	59.9
2011	Ricehub                      	56.88
2010	Hotter Colder                	55.23
2011	Crocodile                    	55.15
2017	The Big Prize                	54.27
2008	Type Printer                 	53.78
2019	Vision Program               	53.44
2012	Crayfish Scrivener           	51.7
2010	Quality of Living            	51.3
2020	Stations                     	51.27
2015	Horses                       	50.57
2020	Counting Mushrooms           	49.65
2008	Linear Garden                	47.6
2015	Sorting                      	47.07
2009	Mecho                        	46.09
2006	Pyramid                      	45.93
2007	Aliens                       	45.92
2015	Boxes with Souvenirs         	44.32
2013	Robots                       	43.53
2010	Maze                         	42.75
2007	Pairs                        	42.26
2016	Unscrambling a Messy Bug     	42.16
2013	Dreaming                     	41.15
2019	Broken Line                  	41.05
2011	Tropical Garden              	40.62
2010	Languages                    	40.08
2014	Wall                         	39.76
2006	The Valley of Mexico         	39.26
2015	Scales                       	37.51
2019	Rectangles                   	36.92
2014	Game                         	36.57
2017	Nowruz                       	34.51
2014	Friend                       	33.36
2010	Saveit                       	33.22
2014	Rail                         	32.71
2013	Art Class                    	32.48
2018	Mechanical Doll              	31.54
2012	Ideal City                   	31.39
2018	Werewolf                     	30.6
2020	Carnival Tickets             	29.6
2012	Pebbling Odometer            	29.52
2013	Wombats                      	29.42
2009	Hiring                       	28.86
2013	Game                         	28
2019	Split the Attractions        	26.63
2011	Elephants                    	26.54
2017	Wiring                       	26.4
2017	Ancient Books                	26.21
2006	Forbidden Subgraph           	26.15
2012	Jousting Tournament          	26.1
2011	Race                         	25.85
2016	Roller Coaster Railroad      	25.53
2020	Packing Biscuits             	22.85
2014	Holiday                      	22.7
2015	Teams                        	22.62
2009	Salesman                     	22.42
2018	Meetings                     	21.71
2007	Flood                        	20.65
2007	Sails                        	19.73
2006	A Black Box Game             	19.11
2012	Parachute Rings              	18.47
2017	Simurgh                      	18.4
2016	Shortcut                     	18.35
2016	Aliens                       	17.86
2008	Islands                      	17.11
2018	Highway Tolls                	15.66
2009	Regions                      	15.06
2020	Comparing Plants             	14.54
2008	Teleporters                  	14.53
2018	Seats                        	14.33
2015	Towns                        	13.42
2019	Sky Walking                  	12.69
2012	Last Supper                  	12.5
2009	Archery                      	11.37
2017	Toy Train                    	10.43
2008	Pyramid Base                 	9.82
2006	Joining Points               	8
2007	Training                     	5.31
2008	Fish                         	3.02

#include <bits/stdc++.h>
#define ll long long
 
using namespace std;
 
inline void io(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}
 
const int MAX_SIZE = 1e5+1;
 
vector<vector<pair<int,int>>> adjList(MAX_SIZE,vector<pair<int,int>>());
vector<map<int,int>> trav(MAX_SIZE,map<int,int>());
 
ll d[MAX_SIZE];
 
long long dijsktra(int n){
	int src = 1,dest = n;
	for(int i=0;i<=n;i++)d[i] = INT_MAX;
	d[src] = 0;
	priority_queue<pair<int,int>> q;
	q.push({0,src});
	while(!q.empty()){
		int v = q.top().second;
		int dis = q.top().first*-1;
		q.pop();
		if(v==n)return dis;
		if(d[v]<dis)continue;
		for(auto e : adjList[v]){
			int to = e.first;
			int len = e.second;
			int t = d[v];
			while(trav[v].find(t)!=trav[v].end())t++;
			t+=len;
			if(t < d[to]){
			//	q.erase({d[to],to});
				d[to] = t;
				q.push({-d[to],to});
			}
		}
	}
	if(d[n]==INT_MAX)d[n]=-1;
	return d[n];
}
 
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++){
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		adjList.at(a).push_back({b,c});
		adjList.at(b).push_back({a,c});
	}
	for(int i=0;i<n;i++){
		int k;
		scanf("%d",&k);
		while(k--){
			int t;
			scanf("%d",&t);
			trav.at(i+1).insert({t,1});
		}
	}
	printf("%d\n",dijsktra(n));
}