#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
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;
}

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];
    int u1 = edge[X].to, v1 = edge[X ^ 1].to;
    int u2 = edge[I].to, v2 = edge[I ^ 1].to;
    
    fprintf(stderr, "(%d, %d): %d\n", u1, v1, edge[X].len);
    fprintf(stderr, "(%d, %d): %d\n", u2, v2, edge[I].len);
    
    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;
}