- #include<bits/stdc++.h>
- using namespace std;
- #define IOS ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);
- #define endl '\n'
- #define double long double
- //#define int long long
- #define mod 1000000007
- #define ll long long
-
- int32_t main()
- {
- #ifndef ONLINE_JUDGE
- freopen("int.txt","r",stdin);
- freopen("out.txt","w",stdout);
- #endif
- int n,M;
- cin>>n>>M;
- vector<vector<pair<int,int>>> g(n+1);
- for(int i = 1;i <= M;i++)
- {
- int u,v,c;
- cin>>u>>v>>c;
- g[u].push_back({v,c});
- g[v].push_back({u,c});
- }
- deque<int> q;
- int s,t;
- cin>>s>>t;
- vector<int> vis(n+1,0);
- vis[s] = 1;
- vector<int> cost(n+1,1e7);
- cost[s] = 0;
- vector<set<int>> clr(n+1);
- for(auto it:g[s])
- {
- cost[it.first] = 0;
- q.push_back(it.first);
- clr[it.first].insert(it.second);
- }
-
- while(!q.empty())
- {
- int p = q.front();
- q.pop_front();
- if(p == t)
- break;
- if(vis[p])
- continue;
- vis[p] = 1;
- for(auto it:g[p])
- {
- if(!vis[it.first])
- {
- if(clr[p].find(it.second)!=clr[p].end())
- {
- if(cost[it.first] > cost[p])
- {
- clr[it.first].clear();
- clr[it.first].insert(it.second);
- }
- else
- if(cost[it.first] == cost[p])
- {
- clr[it.first].insert(it.second);
- }
- cost[it.first] = min(cost[it.first],cost[p]);
- q.push_front(it.first);
- }
- else
- {
- if(cost[it.first] > cost[p] + 1)
- {
- clr[it.first].clear();
- clr[it.first].insert(it.second);
- }
- else
- if(cost[it.first] == cost[p] + 1)
- {
- clr[it.first].insert(it.second);
- }
- cost[it.first] = min(cost[it.first],cost[p] + 1);
- q.push_back(it.first);
-
- }
- }
- }
- }
- cout<<cost[t];
- return 0;
- }