#include <bits/stdc++.h>
#define N 500005

const int INF = 0x3f3f3f3f;

struct edge {
	int u, v, w, l;
	edge (int u0 = 0, int v0 = 0, int w0 = 0, int l0 = 0) : u(u0), v(v0), w(w0), l(l0) {}
	edge * read() {scanf("%d%d%d%d", &u, &v, &w, &l); ++u; ++v; return this;}
} e[N];

int n, q;
int p[N];

inline void up(int &x, const int y) {e[x].w > e[y].w ? x = y : 0;}

namespace LCT {
	#define pa p[nd]
	#define root nd[0].c[0]

	struct node {bool rev; int p, c[2], min, sum;} nd[N];

	inline int dir(int x) {return !x[nd].p ? -1 : x == x[nd].pa.c[0] ? 0 : x == x[nd].pa.c[1] ? 1 : -1;}

	void reverse(int x) {std::swap(x[nd].c[0], x[nd].c[1]); x[nd].rev = !x[nd].rev;}

	void push_down(int x) {if (x[nd].rev) reverse(x[nd].c[0]), reverse(x[nd].c[1]); x[nd].rev = false;}

	void pull_down(int x) {if (~dir(x)) pull_down(x[nd].p); push_down(x);}

	void update(int x) {
		x[nd].min = x;
		up(x[nd].min, x[nd].c[0][nd].min);
		up(x[nd].min, x[nd].c[1][nd].min);
		x[nd].sum = x[nd].c[0][nd].sum + x[nd].c[1][nd].sum + e[x].l;
	}

	void rotate(int x) {
		int y = x[nd].p, d = !dir(x);
		nd[y[nd].c[!d] = x[nd].c[d]].p = y;
		x[nd].p = y[nd].p;
		if(~dir(y)) y[nd].pa.c[dir(y)] = x;
		nd[x[nd].c[d] = y].p = x;
		update(y);
	}

	void splay(int x) {
		for (pull_down(x); ~dir(x); rotate(x))
			if (~dir(x[nd].p)) rotate(dir(x) ^ dir(x[nd].p) ? x : x[nd].p);
		update(x);
	}

	void access(int x) {for(int y = 0; x; y = x, x = x[nd].p){
		splay(x); x[nd].c[1] = y; update(x);}}

	void make_root(int x) {access(x); splay(x); reverse(x);}

	void link(int x, int y) {make_root(x); x[nd].p = y;}

	void split(int x, int y) {make_root(x); access(y); splay(y);}

	void cut(int x, int y) {split(x, y); x[nd].p = y[nd].c[0] = 0; update(y);}

	int query(int x, int y) {split(x, y); return y;}
}

int ancestor(int x) {return x == p[x] ? x : (p[x] = ancestor(p[x]));}

bool test(int x, int y, bool un = false) {
	if ((x = ancestor(x)) == (y = ancestor(y))) return true;
	if (un) p[x] = y; return false;
}

int main() {
	int i, u, v;
	char op[10];
	scanf("%d%d", &n, &q);
	for (i = 0; i <= n; ++i) e[i].w = INF, p[i] = i;
	for (; q; --q)
		switch (scanf("%s", op), *op) {
			case 99: {
				scanf("%d%d", &u, &v); u += n + 1;
				LCT::splay(u); e[u].l = v; LCT::update(u);
				break;
			}
			case 102: {
				scanf("%d", &i); e[i += n + 1].read();
				if (test(e[i].u, e[i].v, true)) {
					LCT::node g = LCT::nd[LCT::query(e[i].u, e[i].v)];
					if (e[g.min].w < e[i].w) LCT::cut(e[g.min].u, g.min), LCT::cut(e[g.min].v, g.min);
					else break;
				}
				LCT::link(e[i].u, i); LCT::link(e[i].v, i);
				break;
			}
			case 109: {
				scanf("%d%d", &u, &v);
				test(++u, ++v) ? printf("%d\n", LCT::nd[LCT::query(u, v)].sum) : puts("-1");
				break;
			}
		}
	return 0;
}