#include <bits/stdc++.h>
using namespace std;
struct vg
{
    long long s1, s2, v, t1, t2;
};
bool cmp(vg a, vg b)
{
    return a.t1 < b.t1;
}
int main()
{
    //freopen("input.txt", "r", stdin);
    long long n, m;
    cin >> n >> m;
    vector<vg> v(m);
    vector<long long> N(n + 1 + 228 + 1337 + 1488);
    for(long long i = 0; i < m; ++i)
    {
        cin >> v[i].s1 >> v[i].s2 >> v[i].v;
        long long t1_h, t2_h, t1_m, t2_m;
        char kek;
        cin >> t1_h >> kek >> t1_m >> t2_h >> kek >> t2_m;
        v[i].t1 = (t1_h) * 60 + t1_m;
        v[i].t2 = (t2_h) * 60 + t2_m;
        if(v[i].t1 > v[i].t2)
        {
            v[i].t2 += 24 * 60;
        }
    }
    sort(v.begin(), v.end(), cmp);
    auto p = v;
    for(auto i : p)
    {
        i.t1 += 24 * 60;
        i.t2 += 24 * 60;
        v.push_back(i);
    }
    sort(v.begin(), v.end(), cmp);
    multiset<pair<long long, pair<long long, long long>>> have_to;
    long long now = 0;
    int cnt = 0;
    long long mx;
    for(auto i : v) {
        if (cnt < n)
        {
            mx = now;
        }
        while(!have_to.empty() && i.t1 >= have_to.begin()->first)
        {
            N[have_to.begin()->second.first] += have_to.begin()->second.second;
            have_to.erase(have_to.begin());
        }
        if(N[i.s1] < i.v)
        {
            now += i.v - N[i.s1];
            N[i.s1] = i.v;
        }
        N[i.s1] -= i.v;
        have_to.insert({i.t2, {i.s2, i.v}});
    }
    cout << min(mx, now);
}