#include <bits/stdc++.h>
#define ll long long

using namespace std;

int read()
{
    int x = 0, f = 1;
    char ch = 0;
    while(!isdigit(ch))
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int N = 1000, M = 2000, INF = 0x3f3f3f3f;

int n, m;
int s, t;

struct Gr
{
    struct Edge
    {
        int v, w, nxt;
    }edge[M + 5];
    int head[N + 5], cnte;
    void adde(int u, int v, int w)
    {
        edge[++cnte] = {v, w, head[u]};
        head[u] = cnte;
    }
}gr;

int rd[N + 5];
stack <int> st;
void hi(int u)
{
    for(int &i = rd[u]; i; )
    {
        int v = gr.edge[i].v, w = gr.edge[i].w;
        i = gr.edge[i].nxt;
        hi(v);
        st.push(w);
    }
}

struct Flo
{
    struct Edge
    {
        int v, c, nxt;
    }edge[(N + M * 3) * 2 + 5];
    int head[N + M + 5], cnte;
    void adde(int u, int v, int c)
    {
        edge[++cnte] = {v, c, head[u]};
        head[u] = cnte;
    }
    Flo()
    {
        cnte = 1;
    }
    void clr()
    {
        cnte = 1;
        for(int i = 1; i <= t; i++)
        {
            head[i] = 0;
        }
    }
}flo;

int dis[N + M + 5];
int rad[N + M + 5];
bool bfs()
{
    queue <int> qu;
    qu.push(s);
    dis[s] = 1;
    while(qu.size())
    {
        int u = qu.front();
        qu.pop();
        rad[u] = flo.head[u];
        for(int i = flo.head[u]; i; i = flo.edge[i].nxt)
        {
            int v = flo.edge[i].v;
            if(!flo.edge[i].c || dis[v])
            {
                continue;
            }
            dis[v] = dis[u] + 1;
            qu.push(v);
        }
    }
    // printf("%d\n", dis[t]);
    return (dis[t] > 0);
}
int dinic(int u, int rem)
{
    if(u == t)
    {
        return rem;
    }
    int tmp = rem;
    for(int i = rad[u]; i; i = flo.edge[i].nxt)
    {
        rad[u] = i;
        int v = flo.edge[i].v;
        if(dis[v] != dis[u] + 1 || !flo.edge[i].c)
        {
            continue;
        }
        int f = dinic(v, min(rem, flo.edge[i].c));
        rem -= f;
        flo.edge[i].c -= f;
        flo.edge[i ^ 1].c += f;
        if(!rem)
        {
            break;
        }
    }
    return tmp - rem;
}
void flowclr()
{
    for(int i = 1; i <= t; i++)
    {
        dis[i] = 0;
    }
}

struct Qu
{
    int u, v, w1, w2;
}qu[M + 5];

int deg[N + 5];
int in[N + 5], out[N + 5];
bool check(int mid)
{
    for(int i = 1; i <= m; i++)
    {
        int u = qu[i].u, v = qu[i].v, w1 = qu[i].w1, w2 = qu[i].w2;
        if(w1 > mid && w2 > mid)
        {
            return 0;
        }
        if(w1 > mid)
        {
            in[u]++, out[v]++;
        }
        else if(w2 > mid)
        {
            out[u]++, in[v]++;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        if(in[i] * 2 > deg[i] || out[i] * 2 > deg[i])
        {
            return 0;
        }
    }
    int sum = 0;
    for(int i = 1; i <= n; i++)
    {
        flo.adde(i, t, deg[i] / 2 - in[i]);
        flo.adde(t, i, 0);
        sum += deg[i] / 2 - in[i];
    }
    for(int i = 1; i <= m; i++)
    {
        int u = qu[i].u, v = qu[i].v, w1 = qu[i].w1, w2 = qu[i].w2;
        if(w1 <= mid && w2 <= mid)
        {
            flo.adde(s, n + i, 1);
            flo.adde(n + i, s, 0);
            flo.adde(n + i, u, 1);
            flo.adde(u, n + i, 0);
            flo.adde(n + i, v, 1);
            flo.adde(v, n + i, 0);
        }
    }
    // printf("\n");
    int flow = 0;
    while(bfs())
    {
        flow += dinic(s, INF);
        flowclr();
    }
    // bfs();
    // dinic(s, INF);
    // printf("%d %d\n", mid, flow);
    if(flow == sum)
    {
        return 1;
    }
    return 0;
}

void checkclr()
{
    for(int i = 1; i <= n; i++)
    {
        in[i] = out[i] = 0;
    }
    flo.clr();
}

void init()
{
    n = read(), m = read();
    s = n + m + 1, t = n + m + 2;
    for(int i = 1; i <= m; i++)
    {
        int u = read(), v = read(), w1 = read(), w2 = read();
        qu[i] = {u, v, w1, w2};
        deg[u]++, deg[v]++;
    }
}

void solve()
{
    for(int i = 1; i <= n; i++)
    {
        if(deg[i] % 2)
        {
            printf("NIE");
            return;
        }
    }
    // check(500);
    int l = 1, r = 1001;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        if(check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
        checkclr();
    }
    if(l == 1001)
    {
        printf("NIE");
        return;
    }
    printf("%d\n", l);
    check(l);
    for(int i = 1; i <= m; i++)
    {
        int u = qu[i].u, v = qu[i].v, w1 = qu[i].w1, w2 = qu[i].w2;
        if(w1 > l)
        {
            gr.adde(v, u, i);
        }
        else if(w2 > l)
        {
            gr.adde(u, v, i);
        }
        else
        {
            for(int j = flo.head[n + i]; j; j = flo.edge[j].nxt)
            {
                int vv = flo.edge[j].v;
                if(!flo.edge[j].c)
                {
                    gr.adde(u + v - vv, vv, i);
                }
            }
        }
    }
    for(int i = 1; i <= n; i++)
    {
        rd[i] = gr.head[i];
    }
    hi(1);
    while(st.size())
    {
        printf("%d ", st.top());
        st.pop();
    }
}

int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("gen.in", "r", stdin);
    freopen("my.out", "w", stdout);
#endif
    init();
    solve();
    return 0;
}

思路是题解的网络流、欧拉回路