/*
#ifndef ONLINE_JUDGE
#include "AkbarKING.h"
#else
#define debug(...)
#define debugArr(...)
#define debugG(...)
#endif
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define $AzH_TxdmN$ ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#define ep emplace_back
#define pb push_back
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define heap pii, vector<pii>, greater<pii>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using __indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using __indexed_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
const int sz = 3e5+9;
const int LOG = 63;
const int MOD = 1e9+7;
const int INF = 1e18;
bool sdp[sz];
int dp[2][sz], rerun[sz];
vector<pii>v[sz];
int n, m;
array<int, 2> start;
array<int, 2> endd;
int run = 0;
void djk(int x)
{
++run; // Run dijkstra on each consecutive start[i] for each 0 <= i < 3
priority_queue<heap> pq;
for (int i = 0; i <= n; ++i)
{
dp[0][i] = INF;
rerun[i] = 0;
dp[1][i] = -1;
}
dp[0][x] = 0;
rerun[x] = 1;
pq.emplace(dp[0][x], x);
while(!pq.empty())
{
int w = pq.top().first;
int node = pq.top().second;
pq.pop();
for (auto to : v[node])
{
if (rerun[to.first] >= 2) continue;
if (sdp[to.first] && dp[0][to.first] >= dp[0][node])
{
dp[0][to.first] = dp[0][node];
pq.emplace(dp[0][to.first], to.first);
dp[1][to.first] = node;
++rerun[to.first];
break;
}
else if (dp[0][to.first] >= dp[0][node] + to.second)
{
dp[0][to.first] = dp[0][node] + to.second;
pq.emplace(dp[0][to.first], to.first);
dp[1][to.first] = node;
++rerun[to.first];
break;
}
}
}
if (run & 1)
{
int lst = endd[0];
while(lst != -1)
{
cout << lst << ' ';
sdp[lst] = 1;
lst = dp[1][lst];
}
cout << endl;
sdp[start[0]] = 1;
}
else
{
int lst = endd[1];
while(lst != -1)
{
cout << lst << ' ';
lst = dp[1][lst];
}
cout << endl;
}
}
void solve()
{
cin >> n >> m >> start[0] >> endd[0] >> start[1] >> endd[1];
for (int i = 0, x, y, z; i < m; ++i)
{
cin >> x >> y >> z;
v[x].ep(y, z);
v[y].ep(x, z);
}
djk(start[0]);
djk(start[1]);
cout << dp[0][endd[1]] << '\n';
}
signed main()
{
$AzH_TxdmN$
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
}
