#include <bits/stdc++.h>
#define ll long long
#define sti string
#define bit(n,i) ((n>>i) &1)
#define maxn 200005
#define fi first
#define se second

using namespace std;

const int INFTY = 1e9 + 1;

int n, m;
int lab[maxn], sz[maxn], parent[maxn], weight[maxn];
int visited;

inline void Minimize(int& Target, int Value)
{
    if (Value < Target) Target = Value;
}

void Init()
{
    for (int u = 1; u <= n; ++u)
    {
        sz[u] = 1;
        parent[u] = 0;
    }
    fill(lab + 1, lab + n + 1, 0);
    visited = 0;
}

void AddChild(int p, int c)
{
    parent[c] = p;
    if (p != 0)
        sz[p] += sz[c];
}

void RemoveChild(int p, int c)
{
    parent[c] = 0;
    sz[p] -= sz[c];
}

void UpTree(int x)
{
    int y = parent[x];
    int z = parent[y];
    if (z != 0)
        RemoveChild(z, y);
    RemoveChild(y, x);
    if (z != 0 && weight[x] < weight[y])
    {
        AddChild(z, x);
        AddChild(z, y);
    }
    else
    {
        AddChild(x, y);
        AddChild(z, x);
        swap(weight[x], weight[y]);
    }
}

void Calibrate(int x)
{
    while (parent[x] != 0)
        if ((ll)sz[x] * 3 > (ll)sz[parent[x]] * 2)
            UpTree(x);
        else
            x = parent[x];
}

int PathMin(int s, int t)
{
    Calibrate(s);
    Calibrate(t);
    int a = 0;
    ++visited;
    for (int i = s; i != 0; i = parent[i]) lab[i] = visited;
    for (int i = t; i != 0; i = parent[i])
        if (lab[i] == visited)
        {
            a = i; break;
        }
    if (a == 0) return -1;
    int res = INFTY;
    for (int i = s; i != a; i = parent[i])
        Minimize(res, weight[i]);
    for (int i = t; i != a; i = parent[i])
        Minimize(res, weight[i]);
    return res;
}

void AddEdge(int u, int v, int b)
{
    int temp = PathMin(u, v);
    if (temp >= b) return;
    while (parent[v] != 0) UpTree(v);
    while (parent[u] != 0) UpTree(u);
    weight[v] = b;
    if (parent[v] != u)
        AddChild(u, v);
}

signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    if(n<=200){
        Init();
        while (m-- > 0)
        {
            int u, v, w, s, t;
            cin >> u >> v >> w >> s >> t;
            AddEdge(u, v, INFTY - w);
            int r = PathMin(s, t);
            if (r == -1) cout << -1 << '\n';
            else cout << INFTY - r << '\n';
        }
    }
    return 0;
}