#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,y,x) for (int i=(y);i>=(x);i--)
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
void file() {
    #ifdef zqj
    freopen("a.in","r",stdin);
    #endif
}
typedef long long ll;
#define sz 101010

int n,m;
vector<pii>V[sz];

int dfn[sz],low[sz],cc;
stack<int>S;
int bel[sz],T;
vector<tuple<int,int,int>>id[sz];
void dfs(int x,int fa) {
    dfn[x]=low[x]=++cc; S.push(x);
    for (auto [v,w]:V[x]) if (v!=fa) {
        if (!dfn[v]) dfs(v,x),chkmin(low[x],low[v]);
        else chkmin(low[x],dfn[v]);
    }
    if (dfn[x]==low[x]) {
        int y; ++T;
        do y=S.top(),S.pop(),bel[y]=T; while (y!=x);
    }
}

struct hh {
    int t,w,nxt;
}edge[sz<<3];
int head[sz],ecnt=1;
void make_edge(int f,int t,int w) {
    edge[++ecnt]=hh{t,w,head[f]};
    head[f]=ecnt;
    edge[++ecnt]={f,w,head[t]};
    head[t]=ecnt;
}
int vis[sz];
int flow(int x,int ww) {
    if (x==n+1) return 1;
    vis[x]=1;
    for (int i=head[x];i;i=edge[i].nxt) if (edge[i].w) {
        int v=edge[i].t;
        if (!vis[v]&&flow(v,ww)) return edge[i].w-=1,edge[i^1].w+=1,1;
    }
    return 0;
}

vector<int>vv[sz];
void getans(int x,vector<int>&ans) {
    ans.push_back(x);
    if (x==n+1) return;
    assert(vv[x].size());
    int y=vv[x].back(); vv[x].pop_back();
    getans(y,ans);
}

int main(){
    file();
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n>>m;
    int x,y,z;
    rep(i,1,m) cin>>x>>y>>z,V[x].push_back({y,z}),V[y].push_back({x,z});
    dfs(1,0);
    rep(x,1,n) for (auto [y,z]:V[x]) if (bel[y]==bel[x]&&x<y) id[bel[x]].push_back({z,x,y});
    int ans=-1,x1,y1,x2,y2;
    rep(i,1,T) if (id[i].size()>1u) {
        auto [z1,x1_,y1_]=*min_element(id[i].begin(),id[i].end());
        auto [z2,x2_,y2_]=*max_element(id[i].begin(),id[i].end());
        if (chkmax(ans,z2-z1)) x1=x1_,y1=y1_,x2=x2_,y2=y2_;
    }
    rep(x,1,n) for (auto [y,z]:V[x]) 
        if (bel[x]==bel[x1]&&bel[y]==bel[x1]&&x<y&&pii{x,y}!=pii{x1,y1}&&pii{x,y}!=pii{x2,y2})
            make_edge(x,y,1);
    int S=0,T=n+1;
    make_edge(S,x1,1),make_edge(S,y1,1),make_edge(x2,T,1),make_edge(y2,T,1);
    rep(_,1,2) assert(flow(S,1)==1),memset(vis,0,sizeof(vis));
    for (int e=2;e<=ecnt;e+=2) if (edge[e].w!=1) {
        int t=edge[e].t,f=edge[e^1].t;
        if (!edge[e].w) vv[f].push_back(t);
        else vv[t].push_back(f);
    }
    vector<int>ans1,ans2;
    getans(S,ans1);
    getans(S,ans2);
    reverse(ans2.begin(),ans2.end());
    cout<<ans<<'\n';
    cout<<ans1.size()+ans2.size()-4<<'\n';
    for (auto x:ans1) if (x!=S&&x!=T) cout<<x<<' ';
    for (auto x:ans2) if (x!=S&&x!=T) cout<<x<<' ';
    return 0;
}