#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include "algo_templates/AdvancedMath.cpp" using namespace std; #pragma comment(linker, "/STACK:36777216") #define For(i,l,r) for (int i = l; i < r + 1; i ++) #define ForI(it , s , T) for (T :: iterator it = s.begin(); it != s.end() ; ++ it ) #define LL long long #define iinf 2000000000 #define linf 2000000000000000000LL #define MOD (1000000007) #define Pi 3.1415926535897932384 #define bit(mask,i) ((mask>>i)&1) #define pb(x) push_back(x) #define mk(x,y) make_pair(x,y) #define sqr(x) ((x)*(x)) #define pause cin.get();cin.get(); #define fir first #define sec second #define ln(x) log(x) #define pii pair #define y1 ysdgdhsdg const int Direction[4][2] = {{-1,0},{0,1},{1,0},{0,-1}}; const int Nmax = 200100; int n , m , k; int start, dist, weight; struct Order { int from, target, weight, cost, number; bool valid; Order(){}; Order(int _f, int _t, int _w, int _c, int _n, bool _valid): from(_f), target(_t), weight(_w), cost(_c), number(_n), valid(_valid){}; bool operator < (Order instance) const { if (this -> from == this -> target && instance.from == instance.target) { return this -> number <= instance.number; } if (this -> from == this -> target) return 1; if (instance.from == instance.target) return 0; return (this -> cost > instance.cost); } }; vector order[Nmax]; int used[Nmax]; LL d[Nmax],cost[Nmax]; vector > > g; struct stat1 { int v; LL dist; stat1(){}; stat1(int _v,LL _dist) : v(_v),dist(_dist){}; bool operator <(stat1 a) const { return this->dist > a.dist; } }; priority_queue que; int parent[Nmax]; void Dijekstra() { int v = -1; while (!que.empty()) { stat1 Cur = que.top(); que.pop(); if (used[Cur.v] || d[Cur.v] != Cur.dist) continue; v = Cur.v; break; } if (v == -1) return ; used[v] = 1; for (int i = 0 ; i < g[v].size(); i ++ ) { int u = g[v][i].first; LL c = g[v][i].second; if (!used[u]) if (d[u] > d[v] + c) { d[u] = d[v] + c; que.push(stat1(u,d[u])); parent[u] = v; } } } int main() { ios_base::sync_with_stdio(0); cin >> n; g.clear(); g.resize(n+1); cin >> m; assert(1 <= n && n <= 100000 && m >= 1 && m <= 100000); For(i,1,m) { int x,y,c; cin >> x >> y >> c; assert(1 <= x && x <= n && 1 <= y && y <= n && c >= 1 && c <= 100); g[x].pb(mk(y,c)); g[y].pb(mk(x,c)); } cin >> k; assert(1 <= k && k <= 100000); for (int i = 1; i <= k; i ++) { int a, b, v, c; cin >> a >> b >> v >> c; order[a].push_back (Order(a,b,v,c,i,1)); } cin >> start >> dist >> weight; assert(1 <= start && start <= n); assert(1 <= dist && dist <= 100000); assert(1 <= weight && weight <= 1000000000); for (int i = 1; i <= n; i ++) sort(order[i].begin(), order[i].end()); vector > ansList; for (int it = 1; it <= 100; it ++) { while (!que.empty()) que.pop(); For(i,1,n) d[i] = linf, used[i] = 0; d[start] = 0; que.push(stat1(start,0)); For(i,1,n) Dijekstra(); For(i,1,n) assert(d[i] != linf); int v = -1; int NUM = -1; for (int i = 0; i < order[start].size(); i ++) { if (!order[start][i].valid) continue; if (d[order[start][i].target] > dist) {order[start][i].valid=0; continue;} if (order[start][i].weight > weight) {order[start][i].valid = 0; continue;} v = order[start][i].target; dist -= d[order[start][i].target]; order[start][i].valid = 0; NUM = order[start][i].number; //cout << 1 << " " << NUM << endl; ansList.push_back(make_pair(1,NUM)); break; } if (v == -1) { int nw = -1; for (int j = 1; j <= n; j ++) for (int k = 0; k < order[j].size(); k ++) { if (order[j][k].valid && order[j][k].weight <= weight) { if (nw == -1 || d[nw] > d[order[j][k].from]) nw = order[j][k].from; } } if (d[nw] > dist) nw = -1; if (nw == -1) break; dist -= d[nw]; int fnsh = nw; vector ans; while (start != nw) ans.pb(nw),nw = parent[nw]; for (int j = ans.size() - 1; j >= 0; j --) ansList.push_back(make_pair(0,ans[j])); start = fnsh; continue; } int tar = v; vector ans; while (v != start) ans.pb(v),v = parent[v]; //ans.push_back(start); for (int i = ans.size() - 1; i >= 0; i -- ) ansList.push_back(make_pair(0, ans[i])); //cout << 0 << " " << ans[i] << endl; ansList.push_back(make_pair(2, NUM)); //cout << 2 << " " << NUM << endl; start = tar; } cout << ansList.size() << endl; for (int i = 0; i < ansList.size(); i ++) { cout << ansList[i].first << " " << ansList[i].second << endl; } return 0; }