#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f;
int n,m;
namespace Tarjan{
	int fst[N],nxt[N<<1],tal[N<<1],val[N<<1],tot;
	int dfn[N],low[N],tod,cnt;
	stack<int> stk;
	int mx[N],mn[N],edcid[N];
	inline void add(int x,int y,int z){
		tal[++tot]=y;val[tot]=z;nxt[tot]=fst[x];fst[x]=tot;
	}
	void tarjan(int x,int in_edge){
		dfn[x]=low[x]=++tod,stk.push(x);
		for(int i=fst[x];i;i=nxt[i]){
			int y=tal[i];
			if(!dfn[y]) tarjan(y,i),low[x]=min(low[x],low[y]);
			else    if(i!=(in_edge^1))  low[x]=min(low[x],dfn[y]);
		}
		if(dfn[x]==low[x]){
			cnt++;
			int y;
			do	y=stk.top(),stk.pop(),edcid[y]=cnt;
			while(y!=x);
		}
	}
	inline int get(){
		for(int i=1;i<=n;i++)   if(!dfn[i]) tarjan(i,0);
		for(int i=1;i<=cnt;i++)	mx[i]=-INF,mn[i]=INF;
		for(int x=1;x<=n;x++){
			for(int i=fst[x];i;i=nxt[i]){
				int y=tal[i],z=val[i];
				if(edcid[x]!=edcid[y]) continue;
				mx[edcid[x]]=max(mx[edcid[x]],z),mn[edcid[x]]=min(mn[edcid[x]],z);
			}
		}
		int ans=0,ret=0;
		for(int i=1;i<=cnt;i++)	if(mx[i]-mn[i]>ans)	ans=mx[i]-mn[i],ret=i;
		cout<<1454939480<<endl;
		return ret;
	}
}
namespace Solve{
	int s,t;
	queue<int> q;
	int dist[N],vis[N];
	int fst[N],nxt[N<<2],tal[N<<2],val[N<<2],tot=1;
	void add(int x,int y,int z){
		tal[++tot]=y,val[tot]=z,nxt[tot]=fst[x],fst[x]=tot;
	}
	bool bfs(){
		memset(dist,0x3f,sizeof dist);
		memset(vis,0,sizeof vis);
		while(q.size()) q.pop();
		q.push(s),dist[s]=0;
		while(q.size()){
			int x=q.front();q.pop();
			if(vis[x])  continue;
			vis[x]=1;
			for(int i=fst[x];i;i=nxt[i]){
				int y=tal[i],z=val[i];
				if(z&&dist[y]>dist[x]+1){//注意对z非零的判断
					dist[y]=dist[x]+1;
					q.push(y);
				}
			}
		}
		return dist[t]!=INF;
	}
	int dinic(int x,int flow){
		if(x==t)    return flow;
		int rest=flow,k;
		for(int i=fst[x];i&&rest;i=nxt[i]){//注意加上&&rest，否则TLE
			int y=tal[i],&z=val[i],&nz=val[i^1];
			if(z&&dist[y]==dist[x]+1){//注意对z非零的判断
				k=dinic(y,min(rest,z));
				if(!k)  dist[y]=INF;
				rest-=k,z-=k,nz+=k;
			}
		}
		return flow-rest;
	}
	void solve(){
		int flow,maxflow=0;
		while(bfs())    while((flow=dinic(s,INF)))  maxflow+=flow;
	}
	vector<int> e[N];
	void print(int x){
		for(int i=2;i<=tot;i+=2)	if(!val[i]){
			int x=tal[i],y=tal[i^1];
			if(x==s||y==s||x==t||y==t)	continue;
			e[x].push_back(y),e[y].push_back(x);
			// cout<<x<<" "<<y<<endl;
		}
		vector<int> ans={x};
		int y=e[x][0],lst=x;
		while(y!=x){
			ans.push_back(y);
			for(int i:e[y])	if(i!=lst){lst=y,y=i;break;}
		}
		cout<<int(ans.size())<<endl;
		for(int i:ans)	cout<<i<<" ";
		cout<<endl;
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	Tarjan::tot=1;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z;cin>>x>>y>>z;
		Tarjan::add(x,y,z),Tarjan::add(y,x,z);
	}
	int id=Tarjan::get();
	int mx=-INF,mn=INF,mxx=0,mxy=0,mnx=0,mny=0;
	for(int x=1;x<=n;x++)	if(Tarjan::edcid[x]==id){
		for(int i=Tarjan::fst[x];i;i=Tarjan::nxt[i]){
			int y=Tarjan::tal[i],z=Tarjan::val[i];
			if(Tarjan::edcid[x]!=Tarjan::edcid[y]) continue;
			if(z>mx)	mx=z,mxx=x,mxy=y;
			if(z<mn)	mn=z,mnx=x,mny=y;
		}
	}
	Solve::s=n+1,Solve::t=n+2;
	Solve::add(n+1,mxx,1),Solve::add(mxx,n+1,0);
	Solve::add(n+1,mxy,1),Solve::add(mxy,n+1,0);
	Solve::add(mnx,n+2,1),Solve::add(n+2,mnx,0);
	Solve::add(mny,n+2,1),Solve::add(n+2,mny,0);
	// cout<<mxx<<" "<<mxy<<" "<<mnx<<" "<<mny<<endl;
	Solve::e[mxx].push_back(mxy),Solve::e[mxy].push_back(mxx);
	Solve::e[mnx].push_back(mny),Solve::e[mny].push_back(mnx);
	for(int x=1;x<=n;x++)	if(Tarjan::edcid[x]==id){
		for(int i=Tarjan::fst[x];i;i=Tarjan::nxt[i]){
			int y=Tarjan::tal[i];
			if(Tarjan::edcid[x]!=Tarjan::edcid[y]) continue;
			if(x==mxx&&y==mxy)	continue;
			if(x==mnx&&y==mny)	continue;
			if(y==mxx&&x==mxy)	continue;
			if(y==mnx&&x==mny)	continue;
			Solve::add(x,y,1),Solve::add(y,x,0);
		}
	}
	Solve::solve();
	Solve::print(mxx);
	return 0;
}