#include<bits/stdc++.h>
using namespace std;
inline static const nullptr_t _={
ios_base::sync_with_stdio(0);
cin.tie(nullptr),cout.tie(nullptr);
return nullptr;
}();
namespace fast_IO{
#define FASTIO
#define IOSIZE 100000
char ibuf[IOSIZE],obuf[IOSIZE];charp1=ibuf,p2=ibuf,p3=obuf;
#define getchar() cin.get()
#define putchar(x) cout.put(x)
#define isspace(ch)(ch<33)
templateinline T read(){T s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();return sw;}templateinline bool read(T&s){s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();return s=w,true;}inline bool read(char&s){while(s=getchar(),isspace(s));return true;}inline bool read(chars){char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))*s++=ch,ch=getchar();s='�00';return true;}templateinline void print(T x){if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+48);}inline void print(char x){putchar(x);}inline void print(charx){while(*x)putchar(x++);}inline void print(const charx){for(int i=0;x[i];i++)putchar(x[i]);}
#ifdef _GLIBCXX_STRING
inline bool read(string&s){s="";char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))s+=ch,ch=getchar();return true;}inline void print(std::string x){for(int i=0,n=x.size();i<n;i++)putchar(x[i]);}
#endif
template<typename T,typename...T1>inline int read(T&a,T1&...other){return read(a)+read(other...);}template<typename T,typename...T1>inline void print(T a,T1...other){print(a);print(other...);}struct Fast_IO{~Fast_IO(){fwrite(obuf,p3-obuf,1,stdout);}}io;templateFast_IO&operator>>(Fast_IO&io,T&b){return read(b),io;}templateFast_IO&operator<<(Fast_IO&io,T b){return print(b),io;}
}using namespace fast_IO;
constexpr int INF=1e9;
int s1,t1,s2,t2,n,m;
int main() {
io>>s1>>t1>>s2>>t2>>n>>m;
vector<vector> graph(n+1, vector(n+1, INF));
for(int i=1;i<=n;i++) graph[i][i]=0;
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
graph[a][b]=c;
}
vector dist1(n+1, INF);
vector dist2(n+1, INF);
dist1[s1] = 0;
dist2[s2] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq1;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq2;
pq1.push({0, s1});
pq2.push({0, s2});
while(!pq1.empty()){
int d = pq1.top().first;
int u = pq1.top().second;
pq1.pop();
if(d > dist1[u]) continue;
for(int v=1; v<=n; v++){
if(dist1[v] > dist1[u] + graph[u][v]){
dist1[v] = dist1[u] + graph[u][v];
pq1.push({dist1[v], v});
}
}
}
while(!pq2.empty()){
int d = pq2.top().first;
int u = pq2.top().second;
pq2.pop();
if(d > dist2[u]) continue;
for(int v=1; v<=n; v++){
if(dist2[v] > dist2[u] + graph[u][v]){
dist2[v] = dist2[u] + graph[u][v];
pq2.push({dist2[v], v});
}
}
}
io<<dist1[t1]<<'
';
vector path1;
path1.emplace_back(t1);
int cur = t1;
while(cur != s1){
for(int i=1; i<=n; i++){
if(graph[i][cur] != INF && dist1[i] + graph[i][cur] == dist1[cur]){
path1.emplace_back(i);
cur = i;
break;
}
}
}
reverse(path1.begin(), path1.end());
for(int i=0; i<path1.size(); i++) io<<path1[i]<<' ';
cout.put(10);
io<<dist2[t2]<<'
';
vector path2;
path2.emplace_back(t2);
cur = t2;
while(cur != s2){
for(int i=1; i<=n; i++){
if(graph[i][cur] != INF && dist2[i] + graph[i][cur] == dist2[cur]){
path2.emplace_back(i);
cur = i;
break;
}
}
}
reverse(path2.begin(), path2.end());
for(int i=0; i<path2.size(); i++) io<<path2[i]<<' ';
cout.put(10);
return 0;
}
