#include <bits/stdc++.h>
using namespace std;
//char buf[1<<21],*p1=buf,*p2=buf,obuf[1<<21],*O=obuf;
//#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define getc getchar
inline int read() {
	char c = getc() , f = 1;
	while (c > '9' || c < '0'){
		if (c == '-')f = -1;
		c = getc();
	}
	int p = 0;
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getc();
	}
	return p * f;
}
struct edge{int fr , to , nxt , val;}e[200005];
bool f[100005];
int n , m , head[100005] , cnt = 1 , low[100005] , dfn[100005] , lsbl , mx[100005] , mi[100005] , num , col[100005] , s[100005] , tp;
vector <int> v1 , v2;
inline void add(int u , int v , int val){
	e[++cnt].to = v;
	e[cnt].fr = u;
	e[cnt].val = val;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}
namespace MF{
	struct edge{int fr , to , nxt , val;}e[500005];
	int cnt = 3 , head[100005] , dep[100005] , s , t , hd[100005];
	inline void adde(int u , int v , int val){
		e[++cnt].to = v;
		e[cnt].val = val;
		e[cnt].nxt = head[u];
		head[u] = cnt;
	}
	inline void add(int u , int v , int val){
		adde(u , v , val);
		adde(v , u , 0);
	}
	inline bool bfs(){
		for (int i = 1;i <= n + 2;++i)dep[i] = 0;
		queue <int> q;
		q.push(s);
		dep[s] = 1;
		while (!q.empty()){
			int u = q.front();
			q.pop();
			for (int i = head[u];i;i = e[i].nxt){
				int to = e[i].to;
				if (e[i].val && !dep[to]){
					dep[to] = dep[u] + 1;
					q.push(to);
					if (to == t)return 1;
				}
			}
		}
		return 0;
	}
	int dfs(int u , int flow){
		if (!flow)return 0;
		if (u == t)return flow;
		int res = flow;
		for (int &i = hd[u];i;i = e[i].nxt){
			int to = e[i].to;
			if (dep[to] == dep[u] + 1 && e[i].val){
				int d = dfs(to , min(res , e[i].val));
				e[i].val -= d;
				e[i ^ 1].val += d;
				res -= d;
				if (!res)break;
			}
		}
		return flow - res;
	}
	inline void dinic(){
		s = n + 1;
		t = n + 2;
		while (bfs()){
			for (int i = 1;i <= n + 2;++i)hd[i] = head[i];
			while (dfs(s , 2));
		}
	}
	inline void solve(){
		queue <int> q1 , q2;
		for (int i = head[n + 1];i;i = e[i].nxt){
			int to = e[i].to;
			if (e[i].val == 0){
				e[i].val = 1;
				if (q1.empty())q1.push(to);
				else q2.push(to);
			}
		}
		while (!q1.empty()){
			int u = q1.front();
			q1.pop();
			if (u <= n)v1.push_back(u);
			for (int i = head[u];i;i = e[i].nxt){
				int to = e[i].to;
				if (!(i & 1) && e[i].val == 0 && e[i ^ 2].val == 0){
					e[i].val = 1;
					e[i ^ 2].val = 1;
					continue;
				}
				if (e[i].val == 0 && !(i & 1)){
					q1.push(to);
					e[i].val = 1;
					break;
				}
			}
		}
		while (!q2.empty()){
			int u = q2.front();
			q2.pop();
			if (u <= n)v2.push_back(u);
			for (int i = head[u];i;i = e[i].nxt){
				int to = e[i].to;
				if (e[i].val == 0 && !(i & 1)){
					q2.push(to);
					e[i].val = 1;
					break;
				}
			}
		}
	}
}
void dfs(int u , int fa){
    dfn[u] = low[u] = ++lsbl;
	s[++tp] = u;
    for (int i = head[u];i;i = e[i].nxt){
        int to = e[i].to;
		if (!dfn[to]){
			dfs(to , u);
			low[u] = min(low[u] , low[to]);
			if (low[to] > dfn[u])f[i / 2] = 1;
		}else if (to != fa)low[u] = min(low[u] , dfn[to]);
	}
}
void dfs1(int u){
	col[u] = num;
	for (int i = head[u];i;i = e[i].nxt){
		int to = e[i].to;
		if (!f[i / 2] && !col[to])dfs1(to);
	}

}
signed main(){
	//freopen (".in" , "r" , stdin);
	//freopen (".out" , "w" , stdout);
	n = read() , m = read();
	for (int i = 1;i <= n;++i){
		mx[i] = -0x3f3f3f3f;
		mi[i] = 0x3f3f3f3f;
	}
	for (int i = 1;i <= m;++i){
		int u = read() , v = read() , val = read();
		add(u , v , val);
		add(v , u , val);
	}
	for (int i = 1;i <= n;++i)
		if (!dfn[i])
			dfs(i , 0);
	for (int i = 1;i <= n;++i){
		if (!col[i]){
			num++;
			dfs1(i);
		}
	}
	int ans = -1 , id = 0;
	for (int i = 2;i <= cnt;++i){
		int u = e[i].fr , v = e[i].to;
		if (col[u] == col[v]){
			mi[col[u]] = min(mi[col[u]] , e[i].val);
			mx[col[u]] = max(mx[col[u]] , e[i].val);
		}
	}
	for (int i = 1;i <= num;++i){
		if (mx[i] - mi[i] > ans){
			ans = mx[i] - mi[i];
			id = i;
		}
	}
	printf ("%d\n" , ans);
	bool fmx = 0 , fmi = 0;
	for (int i = 2;i <= cnt;i += 2){
		int u = e[i].fr , v = e[i].to;
		if (col[u] == id && col[v] == id){
			if (e[i].val == mx[id] && !fmx){
				fmx = 1;
				MF::add(n + 1 , u , 1);
				MF::add(n + 1 , v , 1);
			}else if (e[i].val == mi[id] && !fmi){
				fmi = 1;
				MF::add(u , n + 2 , 1);
				MF::add(v , n + 2 , 1);
			}else{
				MF::add(u , v , 1);
				MF::add(v , u , 1);
			}
			
		}
	}
	MF::dinic();
	MF::solve();
	int sz = v1.size() + v2.size();
	printf ("%d\n" , sz);
	for (auto x : v1)printf ("%d " , x);
	reverse(v2.begin() , v2.end());
	for (auto x : v2)printf ("%d " , x);
	return 0;
}
/*
5 7
1 2 1
1 3 -2
2 3 1
3 4 3
4 5 1
1 5 -1
2 5 2

5 6
1 2 10
1 3 1
2 3 1
3 4 1
3 5 1
4 5 -10
*/