#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;
// }

struct Net_Max_Flow {
	struct Graph {
		struct node {
			int to, flow, cap, nxt;
		} edge[M << 3];
		int tot = 1, head[N];
		inline void add(int u, int v, int w) {
			edge[++tot] = {v, 0, w, head[u]};
			head[u] = tot;
		}
		inline node & operator [] (const int x) {
			return edge[x];
		}
	} xym;
	
	int n;
	
	inline void init(int _n) {
		n = _n, xym.tot = 1;
		memset(xym.head + 1, 0x00, sizeof (int) * n);
	}
	
	inline void add(int u, int v, int fl, bool tag = false) {
		if (!tag) xym.add(u, v, fl), xym.add(v, u, 0);
        else {
            xym.add(u, v, fl), xym.add(v, u, fl);
        }
	}
    
    bool vis[N];
	
    int flow(int u, int T, int lim) {
        if (u == T) return lim;
        vis[u] = true;
        for (int i = xym.head[u]; i; i = xym.edge[i].nxt)
            if (xym.edge[i].flow < xym.edge[i].cap) {
                int v = xym.edge[i].to;
                if (!vis[v] && flow(v, T, lim))
                    return ++xym.edge[i].flow, --xym.edge[i ^ 1].flow, 1;
            }
        return 0;
    }
	
	long long solve(int S, int T) {
		long long flow = 0;
		for (int _ = 1; _ <= 2; ++_) {
            memset(vis, 0x00, sizeof(vis));
            assert(this -> flow(S, T, 1) == 1);
        }
		return flow = 2;
	}
} yzh;

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;
    
    int III = n + 1, XXX = n + 2;
    
    yzh.init(n + 2);
    
    yzh.add(III, u1, 1);
    yzh.add(III, v1, 1);
    yzh.add(u2, XXX, 1);
    yzh.add(v2, XXX, 1);
    
    for (int u = 1; u <= n; ++u)
        if (sccno[u] == idx)
            for (int i = head[u]; i; i = edge[i].nxt) {
                int v = edge[i].to;
                if (sccno[v] != idx) continue;
                if (v > u) continue;
                if (u == u1 && v == v1) continue;
                if (u == v1 && v == u1) continue;
                if (u == u2 && v == v2) continue;
                if (u == v2 && v == u2) continue;
                // puts("dfsdfsdfsdfsdfs");
                // yzh.add(u, v, 1);
                yzh.add(v, u, 1, true);
            }
    
    int res = yzh.solve(III, XXX);
    
    fprintf(stderr, "maxflow = %d\n", res);
    
    assert(res == 2);
    
    int TTTTTTTT = 0;
    
    for (int u = u1; u != XXX; ) {
        ans.push_back(u);
        for (int i = yzh.xym.head[u]; i; i = yzh.xym.edge[i].nxt) {
            int v = yzh.xym.edge[i].to;
            if (yzh.xym.edge[i].flow != 1) continue;
            if (v == III) continue;
            if (v == XXX) {
                TTTTTTTT = u2 ^ v2 ^ u;
            }
            u = v;
            break;
        }
    }
    
    vector<int> tmp;
    for (int u = TTTTTTTT; u != III; ) {
        // printf("u = %d\n", u);
        tmp.push_back(u);
        for (int i = yzh.xym.head[u]; i; i = yzh.xym.edge[i].nxt) {
            int v = yzh.xym.edge[i].to;
            if (yzh.xym.edge[i ^ 1].flow != 1) continue;
            if (v == XXX) continue;
            u = v;
            break;
        }
    }
    // reverse(tmp.begin(), tmp.end());
    
    for (int x : tmp) ans.push_back(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;
}