#include <bits/stdc++.h>
#include <type_traits>
using namespace std;

using ll=int64_t;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) FOR(i,0,b)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
auto& errStream=cerr;
#ifdef LOCAL
#define cerr (cerr<<"-- line "<<__LINE__<<" -- ")
#else
class CerrDummy{}cerrDummy;
template<class T>
CerrDummy& operator<<(CerrDummy&cd,const T&){
	return cd;
}
using charTDummy=char;
using traitsDummy=char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy&cd,basic_ostream<charTDummy,traitsDummy>&(basic_ostream<charTDummy,traitsDummy>&)){
	return cd;
}
#define cerr cerrDummy
#endif
#define REACH cerr<<"reached"<<endl
#define DMP(x) cerr<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))
#define ONE(x) memset(x,-1,sizeof(x))

template<class T> using V=vector<T>;
template<class T> using VV=V<V<T>>;

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	rep(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"(";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<")";
}

ll read(){
	ll i;
	scanf("%"  SCNd64,&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(ll x,int suc=1){
	printf("%" PRId64,x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

template<class T>
void print(const vector<T>&v){
	rep(i,v.size())
		print(v[i],i==int(v.size())-1?1:2);
}

string readString(){
	static char buf[3341000];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341000];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(b<a)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

#define CAPITAL
void Yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<endl;
	#else
	cout<<"Yes"<<endl;
	#endif
	if(ex)exit(0);
}
void No(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<endl;
	#else
	cout<<"No"<<endl;
	#endif
	if(ex)exit(0);
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

constexpr ll TEN(int n){
	return n==0?1:TEN(n-1)*10;
}

template<class T>
vector<T> Uniqued(const vector<T>&vv){
	auto v(vv);
	sort(all(v));
	v.erase(unique(all(v)),v.end());
	return v;
}
template<class T>
void MakeUniqued(vector<T>&v){
	sort(all(v));
	v.erase(unique(all(v)),v.end());
}

//Matroid
//size(): returns size
//Get(): returns pair of
//1. indices of src(vertices that it is free to add)
//2. all (x,y) s.t. del x & add y is possible(y is not a src)
template<class LM,class RM>
struct MatroidIntersection{
	int n,m,s;
	LM& lm;
	RM& rm;
	struct Edge{
		int to,cost,id;
		friend ostream& operator<<(ostream&os,const Edge&e){
			return os<<"{T:"<<e.to<<", C:"<<e.cost<<", I:"<<e.id<<"}";
		}
	};
	V<tuple<int,int,int>> es;
	VV<Edge> g;
	MatroidIntersection(LM& llm,RM& rrm):lm(llm),rm(rrm){
		n=lm.size();
		m=rm.size();
		s=n+m;
	}
	void AddEdge(int a,int b,int c){
		assert(0<=a&&a<n);
		assert(0<=b&&b<m);
		assert(0<=c);
		es.eb(a,b,c);
	}
	vi h;
	V<pi> dist,prev;
	void FindShortest(const vi&src){
		dist.assign(s,pi(inf,-1));
		prev.assign(s,pi(-1,-1));
		
		using Node=tuple<int,int,int>;
		priority_queue<Node,V<Node>,greater<Node>> pq;
		const auto Reach=[&](int v,int d,int step,int j,int k){
			if(pi(d,step)<dist[v]){
				dist[v]=pi(d,step);
				prev[v]=pi(j,k);
				pq.push(make_tuple(d,step,v));
			}
		};
			
		for(auto i:src)
			Reach(i,0,0,-1,-1);
		
		while(!pq.empty()){
			int d,step,v;
			tie(d,step,v)=pq.top();
			pq.pop();
			if(dist[v]!=pi(d,step))
				continue;
			for(auto e:g[v]){
				assert(e.cost+h[v]-h[e.to]>=0);
				Reach(e.to,d+e.cost+h[v]-h[e.to],step+1,v,e.id);
			}
		}
	}
	int Augment(V<bool>&use){
		g.assign(s,V<Edge>());
		vi m1,m2;
		rep(i,es.size()){
			int a,b,c;
			tie(a,b,c)=es[i];
			if(use[i]){
				g[n+b].pb(Edge{a,-c,i});
				m1.pb(a);
				m2.pb(b);
			}else{
				g[a].pb(Edge{n+b,c,i});
			}
		}
		vi src,dst;
		{
			auto w=lm.Get(m1);
			src=w.first;
			if(src.empty())return -1;
			for(auto e:w.second)
				g[e.first].pb(Edge{e.second,0,-1});
		}
		{
			auto w=rm.Get(m2);
			dst=w.first;
			if(dst.empty())return -1;
			for(auto e:w.second)
				g[n+e.second].pb(Edge{n+e.first,0,-1});
		}
		
		FindShortest(src);
		
		pair<pi,int> w(pi(inf/2,-1),-1);
		for(auto i:dst)
			chmin(w,mp(dist[n+i],n+i));
		if(w.second==-1)
			return -1;
		int x=w.second;
		while(prev[x].first!=-1){
			int i=prev[x].second;
			if(i!=-1)
				use[i]=!use[i];
			x=prev[x].first;
		}
		int mn=w.first.first;
		rep(i,s){
			h[i]+=min(dist[i].first,mn);
			chmin(h[i],inf);
		}
		return h[w.second];
	}
	pair<int,vi> Solve(){
		h.assign(s,0);
		V<bool> use(es.size());
		int c=0,f;
		while((f=Augment(use))>=0)
			c+=f;
		vi sol;
		rep(i,es.size())
			if(use[i])
				sol.pb(i);
		return mp(c,sol);
	}
};

struct UnionFind{
	vi rank,par;
	void Init(int n){
		rank.assign(n,0);
		par.assign(n,-1);
	}
	int Find(int i){
		return par[i]==-1?i:(par[i]=Find(par[i]));
	}
	bool Same(int a,int b){
		return Find(a)==Find(b);
	}
	bool Unite(int a,int b){
		a=Find(a);
		b=Find(b);
		if(a==b)
			return false;
		if(rank[a]<rank[b])
			swap(a,b);
		par[b]=a;
		if(rank[a]==rank[b])
			rank[a]++;
		return true;
	}
};

struct MST{
	int n;
	vector<pi> es;
	MST(int nn){
		n=nn;
	}
	void AddEdge(int a,int b){
		assert(0<=a&&a<n);
		assert(0<=b&&b<n);
		es.eb(a,b);
	}
	int size(){
		return es.size();
	}
	UnionFind uf;
	pair<vi,V<pi>> Get(const vi&cur){
		uf.Init(n);
		vi t(size(),0);
		for(auto i:cur){
			uf.Unite(es[i].first,es[i].second);
			t[i]=1;
		}
		vi src;
		rep(i,size())if(!t[i]){
			if(!uf.Same(es[i].first,es[i].second)){
				src.pb(i);
				t[i]=2;
			}
		}
		V<pi> res;
		rep(i,size())if(t[i]==1){
			uf.Init(n);
			rep(j,size())if(t[j]==1&&j!=i)
				uf.Unite(es[j].first,es[j].second);
			rep(j,size())if(!t[j])
				if(!uf.Same(es[j].first,es[j].second))
					res.eb(i,j);
		}
		return mp(src,res);
	}
};

struct FreeMatroid{
	int n;
	FreeMatroid(int nn):n(nn){}
	int size(){
		return n;
	}
	pair<vi,V<pi>> Get(const vi&cur){
		V<bool> used(n);
		for(auto i:cur)
			used[i]=true;
		vi src;
		rep(i,n)if(!used[i])
			src.pb(i);
		return mp(src,V<pi>());
	}
};

signed main(){
	while(1){
		int n=read(),m=read(),k=read();
		if(n==0)break;
		MST mst(n);
		vi cost(m),type(m);
		rep(i,m){
			int u=read()-1,v=read()-1,w=read();
			string l=readString();
			mst.AddEdge(u,v);
			cost[i]=w;
			type[i]=l[0]-'A';
		}
		FreeMatroid fmat(n-1);
		MatroidIntersection<FreeMatroid,MST> matint(fmat,mst);
		rep(i,m){
			if(type[i]==0)
				rep(j,k)
					matint.AddEdge(j,i,cost[i]);
			else
				FOR(j,k,n-1)
					matint.AddEdge(j,i,cost[i]);
		}
		auto ans=matint.Solve();
		if(int(ans.second.size())<n-1)
			print(-1);
		else
			print(ans.first);
	}
}



Measured memory_bytes: 7812