UVa Q11374

//UVa 11374
#include <bits/stdc++.h>
using namespace std;

struct stat{
    int pre, v, w;
    int used;
    bool operator>(const stat &x)const{return w > x.w;}
};
vector<stat> edges[505];
int preV[1005];//1~n := not used, n+1~2n := used

int main(){
    int n,s,e,m,a,b,c;
    bool one = 1;
    while(cin >> n >> s >> e){
        if(one)one = 0;
        else cout << '\n';
        memset(preV, 0, sizeof(preV));
        for(int i = 1; i <= n; ++i)edges[i].clear();
        cin >> m;
        for(int i = 0; i < m; ++i){
            cin >> a >> b >> c;
            stat in={.pre=a, .v=b, .w=c, .used=0};
            edges[a].emplace_back(in);
            in={.pre=b, .v=a, .w=c, .used=0};
            edges[b].emplace_back(in);
        }
        cin >> m;
        for(int i = 0; i < m; ++i){
            cin >> a >> b >> c;
            stat in={.pre=a, .v=b, .w=c, .used=a};
            edges[a].emplace_back(in);
            in={.pre=b, .v=a, .w=c, .used=b};
            edges[b].emplace_back(in);
        }
        priority_queue<stat, deque<stat>, greater<stat>> pq;
        stat tmd = {.pre=-1, .v=s, .w=0, .used=0};
        pq.push(tmd);
        stat ans;
        while(!pq.empty()){
            tmd = pq.top();
            pq.pop();
            //cout << tmd.pre << ' ' << tmd.v << ' ' << tmd.w << ' ' << tmd.used << '\n';
            int idx = (tmd.used)? tmd.v+n : tmd.v;
            if(!preV[idx])preV[idx] = tmd.pre;
            else continue;
            if(tmd.v == e){
                ans = tmd;
                break;
            }
            for(unsigned i = 0; i < edges[tmd.v].size(); ++i){
                stat nxt = edges[tmd.v][i];
                idx = (nxt.used | tmd.used)? nxt.v+n : nxt.v;
                if(!preV[idx] && (tmd.used == 0 || nxt.used == 0)){
                    if(tmd.used > 0)nxt.pre += n;
                    nxt.w += tmd.w;
                    nxt.used |= tmd.used;
                    pq.push(nxt);
                }
            }
        }
        vector<int> out;
        int x = (ans.used)? ans.v+n : ans.v;
        while(x != -1){
            out.emplace_back((x>n)? x-n : x);
            x = preV[x];
        }
        while(!out.empty()){
            cout << out.back();
            out.pop_back();
            if(!out.empty())cout << ' ';
        }
        cout << '\n';
        if(ans.used == 0)cout << "Ticket Not Used";
        else cout << ans.used;
        cout << '\n' << ans.w << '\n';
    }
    return 0;
}