#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 100010, M = 100010;

struct node {
    int to, nxt, len;
} edge[M << 1];
int head[N], tot = 1;
void add(int u, int v, int w) {
    edge[++tot] = {
        .to = v, .nxt = head[u], .len = w
    }, head[u] = tot;
}

int n, m;

int dfn[N], low[N], timer;
int stack[N], top;
int scnt, sccno[N];

void tarjan(int u, int f) {
    dfn[u] = low[u] = ++timer;
    stack[++top] = u;
    for (int i = head[u]; i; i = edge[i].nxt) {
        if ((i ^ f) == 1) continue;
        int v = edge[i].to;
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        ++scnt;
        do {
            int v = stack[top--];
            sccno[v] = scnt;
            // printf("%d: %d\n", scnt, v);
        } while (stack[top + 1] != u);
    }
}

int mx[N], mi[N], xp[N], ip[N];

// bool ins[N << 1], vis[N];
// bool dfs(int u, int fr, vector<int>& vec, int target) {
//     vis[u] = true;
//     if (u == target) return vec.emplace_back(u), true;
//     for (int i = head[u]; i; i = edge[i].nxt) {
//         if (i == (fr ^ 1)) continue;
//         if (ins[i]) continue;
//         int v = edge[i].to;
//         if (vis[v]) continue;
//         bool res = dfs(v, i, vec, target);
//         if (res) {
//             ins[i] = ins[i ^ 1] = true;
//             vec.emplace_back(u);
//             return true;
//         }
//     }
//     return false;
// }

vector<int> ans;
int xxx, iii, u1, u2, v1, v2;
bool intree[M << 1], vis[N];
int FA[N], DOWN;
void dfs(int u, int fr) {
    vis[u] = true;
    if (u == v1) FA[u1] = u, dfs(u1, xxx);
    if (u == u2 && fr != iii) FA[v2] = u, DOWN = v2, dfs(v2, iii ^ 1);
    if (u == v2 && fr != (iii ^ 1)) FA[u2] = u, DOWN = u2, dfs(u2, iii);
    for (int i = head[u]; i; i = edge[i].nxt) {
        if (i == (fr ^ 1)) continue;
        if (i == (xxx ^ 1)) continue;
        if (i == iii) continue;
        if (i == (iii ^ 1)) continue;
        int v = edge[i].to;
        if (vis[v]) continue;
        FA[v] = u;
        intree[i] = intree[i ^ 1] = true;
        dfs(v, i);
    }
}

bool can[N];
int fff[N];

bool dfs(int u) {
    if (can[u]) {
        // printf("fff[5] = %d\n", fff[5]);
        // printf("fff[4] = %d\n", fff[4]);
        for (int x = u; x; x = fff[x])
            ans.emplace_back(x);
        reverse(ans.begin(), ans.end());
        return true;
    }
    for (int i = head[u]; i; i = edge[i].nxt) {
        if (!intree[i]) continue;
        int v = edge[i].to;
        if (v == FA[u]) continue;
        bool rr = dfs(v);
        if (rr) {
            ans.emplace_back(u);
            return true;
        }
    }
    return false;
}

signed main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v, w; i <= m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w), add(v, u, w);
    }
    for (int i = 1; i <= n; ++i)
        if (!dfn[i])
            tarjan(i, 0);
    for (int i = 1; i <= scnt; ++i) {
        mx[i] = -0x3f3f3f3f;
        mi[i] = 0x3f3f3f3f;
    }
    for (int u = 1; u <= n; ++u)
        for (int i = head[u]; i; i = edge[i].nxt) {
            int v = edge[i].to;
            if (sccno[v] != sccno[u]) continue;
            int w = edge[i].len;
            // printf("====== %d\n", w);
            int x = sccno[u];
            if (w > mx[x])
                mx[x] = w, xp[x] = i;
            if (w < mi[x])
                mi[x] = w, ip[x] = i;
        }
    int mm = 0, idx = -1;
    for (int i = 1; i <= scnt; ++i)
        if (mx[i] - mi[i] > mm) {
            mm = mx[i] - mi[i];
            idx = i;
        }
    printf("%d\n", mm);
    int X = xp[idx], I = ip[idx];
    u1 = edge[X].to, v1 = edge[X ^ 1].to;
    u2 = edge[I].to, v2 = edge[I ^ 1].to;
    
    if (u1 == v2) swap(u2, v2), I ^= 1;
    if (v1 == u2) swap(u1, v1), X ^= 1;
    if (v1 == v2) swap(u2, v2), I ^= 1, swap(u1, v1), X ^= 1;
    
    fprintf(stderr, "(%d, %d): %d\n", u1, v1, edge[X].len);
    fprintf(stderr, "(%d, %d): %d\n", u2, v2, edge[I].len);
    
    iii = I, xxx = X;
    
    intree[X] = intree[X ^ 1] = true;
    intree[I] = intree[I ^ 1] = true;
    
    dfs(v1, 0);
    
    // for (int u = 1; u <= n; ++u)
    //     printf(">>> %d %d\n", u, FA[u]);
    
    queue<int> Q;
    Q.push(v1), can[v1] = true;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (int i = head[u]; i; i = edge[i].nxt) {
            if (!intree[i]) continue;
            int v = edge[i].to;
            if (v == FA[u]) continue;
            Q.push(v);
        }
        if (can[u]) {
            for (int i = head[u]; i; i = edge[i].nxt) {
                if (intree[i]) continue;
                int v = edge[i].to;
                if (can[v]) continue;
                can[v] = true;
                fff[v] = u;
            }
        }
    }
    
    // printf("DOWN = %d\n", DOWN);
    
    bool rerrr = dfs(DOWN);
    
    assert(rerrr);
    
    for (int x = FA[DOWN]; FA[x]; x = FA[x])
        ans.emplace_back(x);
    
    // assert(can[DOWN]);
    
    printf("%d\n", int(ans.size()));
    for (int x : ans) printf("%d ", x);
    
    // vector<int> vec1, vec2;
    // ins[X] = ins[X ^ 1] = true;
    // ins[I] = ins[I ^ 1] = true;
    // bool res1 = dfs(u1, 0, vec1, u2);
    // assert(res1);
    // memset(vis, 0x00, sizeof(vis));
    // bool res2 = dfs(v2, 0, vec2, v1);
    // if (!res2) {
    //     swap(u2, v2);
    //     fprintf(stderr, "(%d, %d): %d\n", u1, v1, edge[X].len);
    //     fprintf(stderr, "(%d, %d): %d\n", u2, v2, edge[I].len);
    //     vec1.clear();
    //     memset(vis, 0x00, sizeof(vis));
    //     memset(ins, 0x00, sizeof(ins));
    //     ins[X] = ins[X ^ 1] = true;
    //     ins[I] = ins[I ^ 1] = true;
    //     res1 = dfs(u1, 0, vec1, u2);
    //     assert(res1);
    //     memset(vis, 0x00, sizeof(vis));
    //     res2 = dfs(v2, 0, vec2, v1);
    //     assert(res2);
    // }
    // printf("%d\n", int(vec1.size() + vec2.size()));
    // // assert(res2);
    // for (int x : vec2) printf("%d ", x);
    // for (int x : vec1) printf("%d ", x);
    // // puts("");
    // // reverse(vec2.begin(), vec2.end());
    return 0;
}