Dynamic Maze: Earliest Path and Maximum Diamond Score

In this problem, you are given a dynamic maze in which roads may appear and disappear over time. Some of these roads contain diamonds that yield a certain score when used. The maze is undirected, and the protagonist's position is fixed at node 1. The destination is node n. Each road becomes available during a certain time interval. Specifically, a road with parameters l and r is available at time T if and only if \(l \le T \le r\).

Your task is to determine the smallest integer time \(T\) such that there exists at least one simple path from node 1 to node n using only roads that are available at time \(T\). Moreover, among all possible simple paths at that time, you need to compute the maximum total diamond score that can be obtained by summing the diamond scores on the roads in the path.

If no such time exists, output -1.

inputFormat

The first line contains two integers \(n\) and \(m\) where \(n\) is the number of nodes and \(m\) is the number of roads.

Each of the next \(m\) lines contains five integers \(u\), \(v\), \(l\), \(r\), and \(d\) representing a bidirectional road between nodes \(u\) and \(v\) that is available during the time interval \([l, r]\) (i.e. when \(l \le T \le r\)) and has a diamond score of \(d\).

Nodes are numbered from 1 to \(n\) with node 1 being the start point and node \(n\) being the destination.

outputFormat

If there exists a time \(T\) such that a path from node 1 to node \(n\) exists, output two space-separated integers: the earliest such time \(T\) and the maximum diamond score obtainable along a simple path from 1 to \(n\) at time \(T\). Otherwise, output -1.

sample

3 3
1 2 2 5 10
2 3 3 7 20
1 3 5 5 5

3 30