PROGRAM MAIN
    IMPLICIT NONE
    INTEGER :: N, M, I, MAX, SC
    INTEGER, ALLOCATABLE, DIMENSION(:) :: POS, U, V, W

    READ *, N, M
    ALLOCATE(U(M))
    ALLOCATE(V(M))
    ALLOCATE(W(M))
    ALLOCATE(POS(N))

    DO I = 1, N
        POS(I) = I
    END DO

    DO I = 1, M
        READ *, U(I), V(I), W(I)
    END DO


    MAX = 0
    DO WHILE (POS(1) /= 0)
        SC = 0
        DO I = 1, M
            IF (POS(U(I) + 1) < POS(V(I) + 1)) THEN
                SC = SC + W(I)
            END IF
        END DO
        IF (MAX < SC) THEN
            MAX = SC
        END IF
        CALL NEXT_PERMUTATION(POS, N)
    END DO

    PRINT *, MAX

CONTAINS
    SUBROUTINE NEXT_PERMUTATION(ARRAY, LEN)
        IMPLICIT NONE
        INTEGER, INTENT(IN) :: LEN
        INTEGER, INTENT(INOUT) :: ARRAY(LEN)
        INTEGER :: LEFT, RIGHT, TMP

        LEFT = LEN - 1
        DO WHILE (LEFT >= 1 .AND. ARRAY(LEFT) >= ARRAY(LEFT + 1))
            LEFT = LEFT - 1
        END DO
        IF (LEFT < 1) THEN
            ARRAY = 0
            RETURN
        END IF

        RIGHT = LEN
        DO WHILE (ARRAY(LEFT) >= ARRAY(RIGHT))
            RIGHT = RIGHT - 1
        END DO

        TMP = ARRAY(LEFT)
        ARRAY(LEFT) = ARRAY(RIGHT)
        ARRAY(RIGHT) = TMP

        LEFT = LEFT + 1
        RIGHT = LEN

        DO WHILE (LEFT < RIGHT)
            TMP = ARRAY(LEFT)
            ARRAY(LEFT) = ARRAY(RIGHT)
            ARRAY(RIGHT) = TMP
            LEFT = LEFT + 1
            RIGHT = RIGHT - 1
        END DO

        RETURN

    END SUBROUTINE NEXT_PERMUTATION
END PROGRAM MAIN