def reader(inFile):
    (numStops, numPairs) = tuple(inFile.getInts())
    return (numStops,[tuple(inFile.getInts()) for k in xrange(numPairs)])
 
def f(N,k):
    return k * N - ((k * (k - 1)) / 2)
 
def solver((numStops, routes)):
    cost = sum([r[2] * f(numStops, r[1] - r[0]) for r in routes])
    minCost = 0
    events = [(r[i], i, r[2]) for r in routes for i in xrange(2)]
    events.sort()
    queue = []
    for event in events:
        if event[1] == 0:
            queue += [(event[0], event[2])]
        else:
            numToHandle = event[2]
            while (numToHandle > 0):
                num = min(queue[-1][1], numToHandle)
                minCost += num * f(numStops, event[0] - queue[-1][0])
                numToHandle -= num
                if num == queue[-1][1]:
                    queue = queue[:-1]
                else:
                    queue[-1] = (queue[-1][0], queue[-1][1] - num)
    return (cost - minCost) % 1000002013
 
if __name__ == "__main__":
    from GCJ import GCJ
    GCJ(reader, solver, "/Users/lpebody/gcj/2013_2/a/", "a").run()
 

ZGVmIHJlYWRlcihpbkZpbGUpOgogICAgKG51bVN0b3BzLCBudW1QYWlycykgPSB0dXBsZShpbkZpbGUuZ2V0SW50cygpKQogICAgcmV0dXJuIChudW1TdG9wcyxbdHVwbGUoaW5GaWxlLmdldEludHMoKSkgZm9yIGsgaW4geHJhbmdlKG51bVBhaXJzKV0pCgpkZWYgZihOLGspOgogICAgcmV0dXJuIGsgKiBOIC0gKChrICogKGsgLSAxKSkgLyAyKQoKZGVmIHNvbHZlcigobnVtU3RvcHMsIHJvdXRlcykpOgogICAgY29zdCA9IHN1bShbclsyXSAqIGYobnVtU3RvcHMsIHJbMV0gLSByWzBdKSBmb3IgciBpbiByb3V0ZXNdKQogICAgbWluQ29zdCA9IDAKICAgIGV2ZW50cyA9IFsocltpXSwgaSwgclsyXSkgZm9yIHIgaW4gcm91dGVzIGZvciBpIGluIHhyYW5nZSgyKV0KICAgIGV2ZW50cy5zb3J0KCkKICAgIHF1ZXVlID0gW10KICAgIGZvciBldmVudCBpbiBldmVudHM6CiAgICAgICAgaWYgZXZlbnRbMV0gPT0gMDoKICAgICAgICAgICAgcXVldWUgKz0gWyhldmVudFswXSwgZXZlbnRbMl0pXQogICAgICAgIGVsc2U6CiAgICAgICAgICAgIG51bVRvSGFuZGxlID0gZXZlbnRbMl0KICAgICAgICAgICAgd2hpbGUgKG51bVRvSGFuZGxlID4gMCk6CiAgICAgICAgICAgICAgICBudW0gPSBtaW4ocXVldWVbLTFdWzFdLCBudW1Ub0hhbmRsZSkKICAgICAgICAgICAgICAgIG1pbkNvc3QgKz0gbnVtICogZihudW1TdG9wcywgZXZlbnRbMF0gLSBxdWV1ZVstMV1bMF0pCiAgICAgICAgICAgICAgICBudW1Ub0hhbmRsZSAtPSBudW0KICAgICAgICAgICAgICAgIGlmIG51bSA9PSBxdWV1ZVstMV1bMV06CiAgICAgICAgICAgICAgICAgICAgcXVldWUgPSBxdWV1ZVs6LTFdCiAgICAgICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgICAgIHF1ZXVlWy0xXSA9IChxdWV1ZVstMV1bMF0sIHF1ZXVlWy0xXVsxXSAtIG51bSkKICAgIHJldHVybiAoY29zdCAtIG1pbkNvc3QpICUgMTAwMDAwMjAxMwoKaWYgX19uYW1lX18gPT0gIl9fbWFpbl9fIjoKICAgIGZyb20gR0NKIGltcG9ydCBHQ0oKICAgIEdDSihyZWFkZXIsIHNvbHZlciwgIi9Vc2Vycy9scGVib2R5L2djai8yMDEzXzIvYS8iLCAiYSIpLnJ1bigpCg==