#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define F(i,j,k) for (int i=j;i<=k;++i)

#define D(i,j,k) for (int i=j;i>=k;--i)

#define maxn 1000005

#define inf 0x3f3f3f3f

struct Link_Cut_Tree{

	int ch[maxn][2],fa[maxn],rev[maxn],mn[maxn],val[maxn],sum[maxn],len[maxn];

	int sta[maxn],top;

	bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}

	void update(int x)

	{

		mn[x]=x;

		if (val[mn[ch[x][0]]]<val[mn[x]]) mn[x]=mn[ch[x][0]];

		if (val[mn[ch[x][1]]]<val[mn[x]]) mn[x]=mn[ch[x][1]];

		sum[x]=len[x]+sum[ch[x][0]]+sum[ch[x][1]];

	}

	void pushdown (int x)

	{

		if (rev[x])

		{

			rev[x]^=1;

			rev[ch[x][0]]^=1;

			rev[ch[x][1]]^=1;

			swap(ch[x][0],ch[x][1]);

		}

	}

	void rot(int x)

	{

		int y=fa[x],z=fa[y],l,r;

		if (ch[y][0]==x) l=0; else l=1; r=l^1;

		if (!isroot(y))

		{

			if (ch[z][0]==y) ch[z][0]=x;

			else ch[z][1]=x;

		}

		fa[x]=z; fa[y]=x; fa[ch[x][r]]=y;

		ch[y][l]=ch[x][r]; ch[x][r]=y;

		update(y);update(x);

	}

	void splay(int x)

	{

		top=0;sta[++top]=x;

		for (int i=x;!isroot(i);i=fa[i]) sta[++top]=fa[i];

		while (top) pushdown(sta[top--]);

		while (!isroot(x))

		{

			int y=fa[x],z=fa[y];

			if (!isroot(y))

			{

				if (ch[z][0]==y^ch[y][0]==x) rot(x);

				else rot(y);

			}

			rot(x);

		}

	}

	void access(int x)

	{

		for (int t=0;x;t=x,x=fa[x])

			splay(x),ch[x][1]=t,update(x);

	}

	void makeroot(int x)

	{

		access(x); splay(x); rev[x]^=1;

	}

	int find(int x)

	{

		access(x); splay(x); while (ch[x][0]) x=ch[x][0];

		return x;

	}

	void link(int x,int y)

	{

		makeroot(x);

		fa[x]=y;

	}

	void cut(int x,int y)

	{

		makeroot(x);

		access(y);

		ch[y][0]=0;

		fa[x]=0;

	}

	int query(int x,int y)

	{

		if (find(x)!=find(y)) return -1;

		makeroot(x);access(y);splay(y);

		return sum[y];

	}

	int qmn(int x,int y)

	{

		makeroot(x);access(y);splay(y);

		return mn[y];

	}

	void modify(int x,int l)

	{

		access(x);splay(x);

		len[x]=l;update(x);

	}

}LCT;

int n,m,u[maxn],v[maxn],id,t,l,x,y,in[maxn];

char opt[11];

int main()

{

	scanf("%d%d",&n,&m);

	F(i,0,n) LCT.val[i]=inf;

	F(i,1,m)

	{

		scanf("%s",opt);

		switch(opt[0])

		{

			case 'f':

				scanf("%d",&id); id++;

				scanf("%d%d%d%d",&u[id],&v[id],&t,&l);u[id]++;v[id]++;

				LCT.len[id+n]=l;LCT.val[id+n]=t;LCT.mn[id+n]=id+n;

				if (LCT.find(u[id])!=LCT.find(v[id]))

				{

					LCT.link(id+n,u[id]);

					LCT.link(id+n,v[id]);

					in[id]=1;

				}

				else

				{

					int tmp=LCT.qmn(u[id],v[id]);

					if (LCT.val[tmp]<t)

					{

						LCT.cut(u[tmp-n],tmp);

						LCT.cut(v[tmp-n],tmp);

						in[tmp-n]=0;

						LCT.link(id+n,u[id]);

						LCT.link(id+n,v[id]);

						in[id]=1;

					}

				}

			break;

			case 'm':

				scanf("%d%d",&x,&y);x++;y++;

				printf("%d\n",LCT.query(x,y));

			break;

			case 'c':

				scanf("%d%d",&id,&l); id++;

				if (in[id]) LCT.modify(id+n,l);

			break;

		}

	}

}