#include <bits/stdc++.h>   #pragma GCC optimize( O3 )   #pragma GCC optimize( Ofast )   using namespace std;   vector<vector<int> > vec;   set<vector<int> > myset, vis;   map<vector<int>, int> p;   int32_t main() {     ios_base::sync_with_stdio(0);     cin.tie(0);     cout.tie(0);     int n, m, t, a, b;     cin >> n >> m >> t;     vec.resize(n);     while (m--) {       cin >> a >> b;       a--, b--;       vec[a].push_back(b);       vec[b].push_back(a);     }     while (t--) {       cin >> m >> a >> b;       m--, a--, b--;       myset.insert({m, a, b});     }     vector<int> state, ans;     queue<vector<int> > q;     bool ok = 0;     for (auto it : vec[0]) {       if (it == (n - 1)) {         cout << 1 <<   n  << 1 <<     << n <<   n ;         return 0;       }       q.push({0, it}), vis.insert({0, it});     }     while (!q.empty()) {       vector<int> f = q.front();       q.pop();       for (auto it : vec[f[1]]) {         if (myset.find({f[0], f[1], it}) != myset.end()) continue;         if (vis.find({f[1], it}) != vis.end()) continue;         if (it == (n - 1)) {           ok = 1, state = f;           break;         }         q.push({f[1], it});         p[{f[1], it}] = f[0];         vis.insert({f[1], it});       }       if (ok) break;     }     if (!ok) {       cout << -1;       return 0;     }     ans.push_back(state[1]);     int c = 100005;     while ((state[0] != 0)) {       ans.push_back(state[0]);       t = p[state];       state[1] = state[0], state[0] = t;     }     reverse(ans.begin(), ans.end());     cout << ans.size() + 1 <<   n1  ;     for (auto it : ans) cout << it + 1 <<    ;     cout << n <<   n ;     return 0;   }   