#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back

#define rep(i,a,b) for(int i=a; i<(b); ++i)
#define FOR(i,a,b) for(int i=a; i<(b); ++i)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int N = 100005;
int n, m;
vector<vector<pii>> edge;

int cnt = 0;
int comp[N];
vvi node_in_comp;
vector<vector<pii>> edge_in_comp;

int t = 0;
int idx[N], lowlink[N];
stack<int> stk;

void dfs(int u, int p) {
    idx[u] = lowlink[u] = ++t;
    stk.push(u);

    for(pii e: edge[u]) {
        int v = e.x;
        if(v == p) continue;

        if(idx[v]) lowlink[u] = min(lowlink[u], idx[v]);
        else {
            dfs(v, u);
            lowlink[u] = min(lowlink[u], lowlink[v]);
        }
    }

    if(idx[u] == lowlink[u]) {
        node_in_comp.eb();
        while(1) {
            int x = stk.top();
            stk.pop();
            comp[x] = cnt;
            node_in_comp[cnt].eb(x);
            if(x == u) break;
        }
        ++cnt;
    }
}

// =======================================================

ll max_range = -1e18;
vector<int> ans;

struct edge_ {
    int v, cap, pos, num;
    edge_(int _v, int _cap, int _pos, int _num) {
        v = _v;
        cap = _cap;
        pos = _pos;
        num = _num;
    }
};

vector<vector<edge_>> g;
queue<int> bfs;
int dp[N], from[N];
int used[N];
int edge_count;

void add_edge(int a, int b, int c, bool oneway = false) {
    int posa = sz(g[a]);
    int posb = sz(g[b]);
    g[a].eb(b, 1, posb, edge_count);
    if(!oneway) g[b].eb(a, 1, posa, edge_count);
    else g[b].eb(a, 0, posa, edge_count);
    ++edge_count;
}

void st(int source, int sink, int c) {
    for(int e : node_in_comp[c]) {
        dp[e] = -1;
        from[e] = -1;
    }
    dp[sink] = from[sink] = -1;
    dp[source] = 0;
    from[source] = -1;

    bfs.push(source);
    while(!bfs.empty()) {
        int u = bfs.front();
        bfs.pop();
        for(edge_ &e : g[u]) {
            if(e.cap == 0) continue;
            if(dp[e.v] != -1) continue;
            dp[e.v] = dp[u]+1;
            from[e.v] = u;
            bfs.push(e.v);
        }
    }
}

void augment(int source, int sink) {
    int now = sink;
    assert(from[sink] != -1);
    while(now != source) {
        int next = from[now];
        for(edge_ &e: g[next]) {
            if(e.v == now) {
                assert(e.cap > 0);
                e.cap--;
                g[now][e.pos].cap++;
                used[e.num] ^= 1;
                break;
            }
        }
        now = next;
    }
}

vi temp_path;
void dfs_path(int now) {
    if(now < n) {
        temp_path.pb(now);
    }
    for(edge_ &e: g[now]) {
        if(used[e.num]) {
            used[e.num] ^= 1;
            dfs_path(e.v);
            break;
        }
    }
}

vi find_path(pair<pii,int> Max, pair<pii,int> Min) {
    if(Max.x.x > Max.x.y) swap(Max.x.x, Max.x.y);
    if(Min.x.x > Min.x.y) swap(Min.x.x, Min.x.y);

    int cur = comp[Max.x.x];
    int comp_sz = sz(node_in_comp[cur]);
    int source = n;
    int sink = n+1;

    // add edge
    for(int u : node_in_comp[cur]) {
        for(auto e : edge_in_comp[u]) {
            int v = e.x;
            if(u > v) continue;
            if(pii(u,v) == Max.x || pii(u,v) == Min.x) {
                continue;
            }
            add_edge(u, v, 1);
        }
    }
    add_edge(source, Max.x.x, 1, true);
    add_edge(source, Max.x.y, 1, true);
    add_edge(Min.x.x, sink, 1, true);
    add_edge(Min.x.y, sink, 1, true);
   
    // bfs twice
    rep(i,0,2){
        st(source, sink, cur);
        augment(source, sink);
    }
    
    // find path
    temp_path.clear();
    dfs_path(source);

    // TODO: clean up
    rep(i, 0, edge_count) {
        used[i] = 0;
    }
    edge_count = 0;
    g[source].clear();
    g[sink].clear();
    for(int u : node_in_comp[cur]) {
        g[u].clear();
    }

    // debug
    /*
    printf("Comp: ");
    for(int u: node_in_comp[cur]) printf("%d ",u);
    puts("");
    printf("Max: (%d,%d),%d\n",Max.x.x,Max.x.y,Max.y);
    printf("Min: (%d,%d),%d\n",Min.x.x,Min.x.y,Min.y);
    printf("Path: ");
    for(int u: temp_path) {
        printf("%d ",u);
    }
    puts("");
*/
    return temp_path;
}

set<pii> edges;
set<pii> exist_edge;

void solve() {
    scanf("%d %d",&n,&m);

    edge.resize(n);
    edge_in_comp.resize(n);
    g.resize(n+2);

    rep(i, 0, m) {
        int a, b, c;
        scanf("%d %d %d",&a,&b,&c);
        --a;
        --b;
        edge[a].eb(b,c);
        edge[b].eb(a,c);
        if(a > b) swap(a,b);
        exist_edge.emplace(a,b);
    }

    dfs(0, -1);
    
    rep(i, 0, cnt) {
        if(sz(node_in_comp[i]) < 3) continue;
        // find max edge, min edge
        pair<pii,int> Max(pii(0,0),-(1<<30)), Min(pii(0,0),(1<<30));
        for(int u : node_in_comp[i]) {
            for(pii e : edge[u]) {
                if(comp[e.x] == comp[u]) {
                    edge_in_comp[u].pb(e);
                    if(e.y > Max.y) Max = {pii(u,e.x),e.y};
                    if(e.y < Min.y) Min = {pii(u,e.x),e.y};
                }
            }
        }

        if(max_range < Max.y-Min.y) {
            // Find path
            if(Max.x == Min.x) {
                bool found= false;
                if(Max.x.x > Max.x.y) swap(Max.x.x,Max.x.y);
                for(int u : node_in_comp[i]) {
                    for(pii e : edge[u]) {
                        if(comp[e.x] == comp[u]) {
                            int a = u;
                            int b = e.x;
                            if(a > b) swap(a,b);
                            if(pii(a,b) != Max.x){ 
                                Min.x = pii(a,b);
                                found = true;
                                break;
                            }
                        }
                    }
                    if(found) break;
                }
            }
            ans = find_path(Max, Min);
            max_range = Max.y-Min.y;
        }
    }

    rep(i, 0, sz(ans)) {
        int a = ans[i];
        int b= ans[(i+1)%sz(ans)];
        if(a > b) swap(a,b);
        //printf("(%d, %d)\n",a,b);
        //assert(exist_edge.find(pii(a,b)) != exist_edge.end());
        assert(edges.find(pii(a,b)) == edges.end());
        edges.emplace(a,b);
    }

    printf("%lld\n",max_range);
    printf("%d\n",sz(ans));
    for(int e : ans) printf("%d ",e+1);
}

int main() {
    solve();
    return 0;
}