#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define fastio                   \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define multi \
    int _;    \
    cin >> _; \
    while (_--)
#define debug(x) cerr << #x << " = " << (x) << endl;
#define int long long
#define pb push_back
#define eb emplace_back
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
void test() { cerr << "\n"; }
template <typename T, typename... Args>
void test(T x, Args... args) {
    cerr << x << " ";
    test(args...);
}
const ll MOD = 998244353;
// const ll MOD = 1e9+7;
const ll P1 = 999971, base1 = 101;
const ll P2 = 999973, base2 = 103;
const ll N = 2005;
// head

vector<pair<int, int> > e[2005];
int dis[N][3], fa[N][3], dep[N][3], fa1[N][25], fa2[N][25];
bool vis[N][3];

void dijsktra(int s, int idx) {
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
    dis[s][idx] = 0;
    q.push({ dis[s][idx], s });
    while (!q.empty()) {
        auto [_, x] = q.top();
        q.pop();
        if (vis[x][idx])
            continue;
        vis[x][idx] = 1;
        for (auto [y, w] : e[x]) {
            if (vis[y][idx])
                continue;
            if (dis[x][idx] + w < dis[y][idx]) {
                dep[y][idx] = dep[x][idx] + 1;
                fa[y][idx] = x;
                dis[y][idx] = dis[x][idx] + w;
                q.push({ dis[y][idx], y });
            }
        }
    }
}

int lca1(int x, int y) {
    // 令 y 比 x 深。
    // cout << x << ":" << y << endl;
    if (dep[x][1] > dep[y][1])
        swap(x, y);
    // 令 y 和 x 在一个深度。
    int tmp = dep[y][1] - dep[x][1];
    for (int j = 0; tmp; ++j, tmp >>= 1)
        if (tmp & 1)
            y = fa1[y][j];
    // cout << x << ":" << y << endl;
    // cout << x << ":" << y << endl;
    if (y == x)
        return x;
    // 不然的话，找到第一个不是它们祖先的两个点。
    for (int j = 22; j >= 0 && y != x; --j) {
        if (fa1[x][j] != fa1[y][j]) {
            x = fa1[x][j];
            y = fa1[y][j];
        }
    }
    x = fa1[x][0];
    // 返回结果。
    return x;
}

int lca2(int x, int y) {
    // 令 y 比 x 深。
    // cout << x << ":" << y << endl;
    // cout << dep[x][1] << ":" << dep[y][1] << endl;
    if (dep[x][2] > dep[y][2])
        swap(x, y);
    // 令 y 和 x 在一个深度。
    int tmp = dep[y][2] - dep[x][2];
    for (int j = 0; tmp; ++j, tmp >>= 1)
        if (tmp & 1)
            y = fa2[y][j];
    // cout << x << ":" << y << endl;
    if (y == x)
        return x;
    // 不然的话，找到第一个不是它们祖先的两个点。
    for (int j = 22; j >= 0 && y != x; --j) {
        if (fa2[x][j] != fa2[y][j]) {
            x = fa2[x][j];
            y = fa2[y][j];
        }
    }
    x = fa2[x][0];
    // 返回结果。
    return x;
}

signed main() {
    fastio freopen("1.in", "r", stdin);
    int n, m, ans = 1e18;
    cin >> n >> m;
    memset(dis, 127, sizeof(dis));
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        e[u].pb({ v, w });
        e[v].pb({ u, w });
    }
    dijsktra(1, 1);
    dijsktra(n, 2);
    for (int i = 1; i <= n; i++) {
        cout << dep[i][1] << " \n"[i == n];
    }
    for (int i = 1; i <= n; i++) {
        cout << dep[i][2] << " \n"[i == n];
    }
    for (int i = 1; i <= n; i++) {
        fa1[i][0] = fa[i][1];
        fa2[i][0] = fa[i][2];
    }
    for (int j = 1; j <= 24; j++) {
        for (int i = 1; i <= n; i++) {
            fa1[i][j] = fa1[fa1[i][j - 1]][j - 1];
            fa2[i][j] = fa2[fa2[i][j - 1]][j - 1];
        }
    }
    for (int j = 0; j <= 3; j++)
        for (int i = 1; i <= n; i++) {
            cout << fa1[i][j] << " \n"[i == n];
        }
    for (int x = 1; x <= n; x++) {
        for (int y = 1; y <= n; y++) {
            if (x == y)
                continue;
            int l1 = lca1(x, y);
            int l2 = lca2(x, y);
            // debug(x);
            // debug(y);
            // debug(l1);
            // debug(l2);
            if ((l1 == x || l1 == y) && (l2 == x || l2 == y)) {
                continue;
            }
            int cnt = dis[x][1] + dis[y][1] - dis[l1][1] + dis[x][2] + dis[y][2] - dis[l2][2];
            test(dis[x][1], dis[y][1], dis[l1][1], dis[x][2], dis[y][2], dis[l2][2]);
            ans = min(ans, cnt);
        }
    }
    cout << ans << "\n";
    return 0;
}