#include
#include
#include
#include
using namespace std;
const int INF = INT_MAX;
void floyd(vector<vector>& graph, vector<vector>& path) {
int n = graph.size();
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][k] != INF && graph[k][j] != INF && graph[i][k] + graph[k][j] < graph[i][j]) {
graph[i][j] = graph[i][k] + graph[k][j];
path[i][j] = path[i][k];
}
}
}
}
}
void printPath(vector<vector>& path, int start, int end) {
vector p;
int cur = start;
while (cur != end) {
p.push_back(cur);
cur = path[cur][end];
}
p.push_back(end);
for (int i = 0; i < p.size(); i++) {
cout << p[i] << " ";
}
cout << endl;
}
int main() {
int s1, t1, s2, t2;
cin >> s1 >> t1 >> s2 >> t2;
int n, m;
cin >> n >> m;
vector<vector> graph(n, vector(n, INF));
vector<vector> path(n, vector(n, -1));
for (int i = 0; i < n; i++) {
graph[i][i] = 0;
}
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
graph[a - 1][b - 1] = c;
graph[b - 1][a - 1] = c;
path[a - 1][b - 1] = b - 1;
path[b - 1][a - 1] = a - 1;
}
floyd(graph, path);
if (graph[s1 - 1][t1 - 1] == INF) {
cout << -1 << endl;
} else {
cout << graph[s1 - 1][t1 - 1] << endl;
printPath(path, s1 - 1, t1 - 1);
}
if (graph[s2 - 1][t2 - 1] == INF) {
cout << -1 << endl;
} else {
cout << graph[s2 - 1][t2 - 1] << endl;
printPath(path, s2 - 1, t2 - 1);
}
return 0;
