#include<bits/stdc++.h>
#define rep(i,n) for(int i=1;i<=n;i++)
#define rwp(i,l,r) for(int i=l;i<=r;i++)
#define int long long
#define endl '\n'
#define pp push_back
#define pr pair<int,int>
#define x first
#define y second

using namespace std;
const int N=2e5+5;
const int mod=1e9+7;
int x,y,z,n,m,k,t;
string s;
int trs,w,_trans;
int Dis[25][25],Dp[30][60000];
int Bit[30],Val[60000];

struct node {
    int u,v,l,r;
    node(){}
    void input() {
        cin>>u>>v>>l>>r;
    }
} no[20];

void init() {
    cin>>n>>m>>trs;
    rep(i,n) rep(j,n) if(i^j) Dis[i][j]=mod;
    rep(i,m) {
        cin>>x>>y>>w;
        Dis[x][y]=min(Dis[x][y],w);
    }
    rep(i,n) rep(j,n) rep(k,n) {
        Dis[j][k]=min(Dis[j][k],Dis[j][i]+Dis[i][k]);
    }
    rep(i,trs) no[i].input();
    Bit[1]=1;
    for(int i=2;i<=trs;i++)
        Bit[i]=Bit[i-1]*3;
    _trans=Bit[trs]*3;
    for(int trans=0;trans<_trans;trans++) {
        Val[trans]=Val[trans/3];
        if(trans%3==2) Val[trans]++;
        //cout<<Val[trans]<<endl;
    }
    rep(i,n) rep(trans,_trans) Dp[i][trans-1]=mod;
    Dp[1][0]=0;
}

void make_trans_1(int i,int trans) {
    int v=no[i].v;
    for(int u=1;u<=n;u++) {
        int t=Dp[u][trans-Bit[i]];
        t=max(t+Dis[u][no[i].u],no[i].l);
        if(t>no[i].r) continue;
        Dp[no[i].u][trans]=min(Dp[no[i].u][trans],t);
    }
}
int ans=0;

void make_trans_2(int i,int trans) {
    int v=no[i].v;
    for(int u=1;u<=n;u++) {
        int t=Dp[u][trans-Bit[i]];
        t+=Dis[u][v];
        if(t>no[i].r) continue;
        Dp[v][trans]=min(Dp[v][trans],t);
        ans=max(ans,Val[trans]);
    }
}

void solve() {
    init();
    for(int trans=0;trans<_trans;trans++) {
        int tmp=trans;
        rep(i,trs) {
            int t=tmp%3;
            if(t==1) make_trans_1(i,trans);
            if(t==2) make_trans_2(i,trans);
            tmp/=3;
        }
    }
    cout<<ans<<endl;
}

signed main() {
    ios::sync_with_stdio(false);
    //int T;cin>>T;
    //while(T--)
        solve();
}