#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define uint unsigned
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 100100;
const int maxm = 1000100;
const int inf = 0x3f3f3f3f;

int n, m, dfn[maxn], low[maxn], tim, scc[maxn], cnt, stk[maxn], top;
pii f[maxn], g[maxn];

struct node {
	int u, v, d;
} a[maxn];

vector<int> G[maxn];

void dfs(int u, int fa) {
	dfn[u] = low[u] = ++tim;
	stk[++top] = u;
	for (int i : G[u]) {
		int v = u ^ a[i].u ^ a[i].v;
		if (i == fa) {
			continue;
		}
		if (!dfn[v]) {
			dfs(v, i);
			low[u] = min(low[u], low[v]);
		} else {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (dfn[u] == low[u]) {
		++cnt;
		while (1) {
			int x = stk[top--];
			scc[x] = cnt;
			if (x == u) {
				break;
			}
		}
	}
}

int nt, S, T, hd[maxm], len = 1;
struct edge {
	int to, next, cap, flow;
} edges[maxm];

inline void add_edge(int u, int v, int c, int f) {
	edges[++len].to = v;
	edges[len].next = hd[u];
	edges[len].cap = c;
	edges[len].flow = f;
	hd[u] = len;
}

struct Dinic {
	int d[maxn], cur[maxn];
	bool vis[maxn];
	
	inline void add(int u, int v, int c) {
		add_edge(u, v, c, 0);
		add_edge(v, u, 0, 0);
	}
	
	inline bool bfs() {
		queue<int> q;
		for (int i = 1; i <= nt; ++i) {
			vis[i] = 0;
			d[i] = -1;
		}
		q.push(S);
		vis[S] = 1;
		d[S] = 0;
		while (q.size()) {
			int u = q.front();
			q.pop();
			for (int i = hd[u]; i; i = edges[i].next) {
				edge &e = edges[i];
				if (!vis[e.to] && e.cap > e.flow) {
					vis[e.to] = 1;
					d[e.to] = d[u] + 1;
					q.push(e.to);
				}
			}
		}
		return vis[T];
	}
	
	int dfs(int u, int a) {
		if (u == T || !a) {
			return a;
		}
		int flow = 0, f;
		for (int &i = cur[u]; i; i = edges[i].next) {
			edge &e = edges[i];
			if (d[e.to] == d[u] + 1 && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
				e.flow += f;
				edges[i ^ 1].flow -= f;
				flow += f;
				a -= f;
				if (!a) {
					break;
				}
			}
		}
		return flow;
	}
	
	inline int solve() {
		int flow = 0;
		while (bfs()) {
			for (int i = 1; i <= nt; ++i) {
				cur[i] = hd[i];
			}
			flow += dfs(S, inf);
		}
		return flow;
	}
} solver;

int b[maxn], c[maxn], t1, t2, d[maxn];

inline void bfs() {
	queue<int> q;
	q.push(S);
	mems(d, -1);
	d[S] = 0;
	while (q.size()) {
		int u = q.front();
		q.pop();
		for (int i = hd[u]; i; i = edges[i].next) {
			edge &e = edges[i];
			if (e.cap == 1 && e.flow == 1 && d[e.to] == -1) {
				d[e.to] = d[u] + 1;
				q.push(e.to);
			}
		}
	}
	assert(d[T] != -1);
}

void dfs2(int u, int fa) {
	if (u <= n) {
		b[++t1] = u;
	}
	for (int i = hd[u]; i; i = edges[i].next) {
		int v = edges[i].to;
		if (v == fa || !edges[i].flow || d[v] != d[u] + 1) {
			continue;
		}
		edges[i].flow = 0;
		dfs2(v, u);
		break;
	}
}

void dfs3(int u, int fa) {
	if (u <= n) {
		c[++t2] = u;
	}
	for (int i = hd[u]; i; i = edges[i].next) {
		int v = edges[i].to;
		if (v == fa || !edges[i].flow || d[v] != d[u] + 1) {
			continue;
		}
		edges[i].flow = 0;
		dfs3(v, u);
		break;
	}
}

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d%d", &a[i].u, &a[i].v, &a[i].d);
		G[a[i].u].pb(i);
		G[a[i].v].pb(i);
	}
	dfs(1, -1);
	for (int i = 1; i <= cnt; ++i) {
		f[i] = mkp(-inf, 0);
		g[i] = mkp(inf, 0);
	}
	for (int u = 1; u <= n; ++u) {
		for (int i : G[u]) {
			int v = u ^ a[i].u ^ a[i].v, d = a[i].d;
			if (scc[u] == scc[v]) {
				f[scc[u]] = max(f[scc[u]], mkp(d, i));
				g[scc[u]] = min(g[scc[u]], mkp(d, i));
			}
		}
	}
	int mx = -inf, p = -1;
	for (int i = 1; i <= cnt; ++i) {
		int v = f[i].fst - g[i].fst;
		if (v > mx) {
			mx = v;
			p = i;
		}
	}
	printf("%d\n", mx);
	S = n + 1;
	T = nt = n + 2;
	int x = f[p].scd, y = g[p].scd;
	solver.add(S, a[x].u, 1);
	solver.add(S, a[x].v, 1);
	solver.add(a[y].u, T, 1);
	solver.add(a[y].v, T, 1);
	for (int u = 1; u <= n; ++u) {
		for (int i : G[u]) {
			if (i == x || i == y) {
				continue;
			}
			int v = u ^ a[i].u ^ a[i].v;
			if (u < v) {
				solver.add(u, v, 1);
				solver.add(v, u, 1);
			}
		}
	}
	solver.solve();
	bfs();
	dfs2(S, -1);
	bfs();
	dfs3(S, -1);
	// assert(b[t1] == a[y].u || b[t1] == a[y].v);
	// assert(c[t2] == a[y].u || c[t2] == a[y].v);
	printf("%d\n", t1 + t2);
	reverse(c + 1, c + t2 + 1);
	for (int i = 1; i <= t1; ++i) {
		printf("%d ", b[i]);
	}
	for (int i = 1; i <= t2; ++i) {
		printf("%d%c", c[i], " \n"[i == t2]);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}