미르코가 이기는 경주 코스

다브로비나 돈야 그랑프리에 출전한 선수는 미르코와 슬라브코 두 명뿐이다. 경주는 근처 마을을 도는 방식으로 열리고, 마을은 일방통행 도로로 이어져 있다. 도로 $i$에는 미르코가 그 도로를 지나는 데 걸리는 시간 $M_i$와 슬라브코가 걸리는 시간 $S_i$가 정해져 있다.

경주 코스는 어떤 마을에서 출발해 같은 마을로 돌아오는 순환 코스다. 코스에 포함된 도로의 $M_i$를 모두 더한 값이 미르코의 기록이고, $S_i$를 모두 더한 값이 슬라브코의 기록이다. 미르코의 기록이 슬라브코의 기록보다 작으면 그 코스에서는 미르코가 이기고, 두 기록의 차이가 미르코가 앞선 시간이다.

코스는 아직 정해지지 않았다. 미르코는 주최 측을 매수해서, 미르코가 이기는 코스 중 도로 수가 가장 적은 코스를 고르게 만들었다. 그런 코스가 여러 개면 주최 측은 미르코가 앞선 시간이 가장 큰 코스를 고른다.

첫째 줄에 마을의 수 $N$과 도로의 수 $M$이 주어진다. ($2 \le N \le 300$, $2 \le M \le N(N-1)$)

다음 $M$개 줄에 도로 하나의 정보인 네 정수 $A_i$, $B_i$, $M_i$, $S_i$가 주어진다. ($1 \le A_i, B_i \le N$, $A_i \ne B_i$, $0 \le M_i, S_i \le 10^6$) 이 도로는 마을 $A_i$에서 마을 $B_i$로 가는 일방통행이고, 지나는 데 미르코는 $M_i$, 슬라브코는 $S_i$의 시간이 걸린다. 같은 마을 쌍을 같은 방향으로 잇는 도로가 두 개 이상 주어지는 경우는 없다.

미르코가 이기는 순환 코스가 적어도 하나 존재한다.

주최 측이 고른 코스의 도로 수와 그 코스에서 미르코가 앞선 시간을 공백으로 구분해 한 줄에 출력한다.