Model Railroad

Since childhood you have been fascinated by model railroads. Designing your own tracks, complicated junctions and stations with miniature travellers, operators and luggage is a lot of fun. It also takes a lot of space. Your house is more than full by now, so you decide to move the layout into the garden.

You have already carried every finished track outside when you notice an important flaw. The tracks used to sit in different rooms, so there are stations that cannot be reached from each other. That has to change.

The positions of the stations are already fixed, so you know the length of every connection you could build and which connections are already built. Every connection can be used in both directions. You may tear up any set of the connections that are already built and instead build connections whose total length is at most the total length of what you tore up. Decide whether the railroad can be rearranged so that every station is reachable from every other station.

The input consists of:

• one line with three integers $n$ ($2 \le n \le 5 \times 10^4$), $m$ ($0 \le m \le 2.5 \times 10^5$) and $\ell$ ($0 \le \ell \le m$), where $n$ is the number of stations, $m$ is the number of possible connections and $\ell$ is the number of connections that are already built;
• $m$ lines, each with three integers $a$, $b$ ($1 \le a, b \le n$) and $c$ ($0 \le c \le 5 \times 10^3$), describing a connection between station $a$ and station $b$ of length $c$.

The first $\ell$ of those connections already exist. Both endpoints of a connection may be the same station, and the same pair of stations may appear more than once.

Print possible if every station can end up reachable from every other station, and impossible otherwise.

The first sample case is drawn in Figure E.1. You can connect all stations by tearing up the connection of length 2 between stations 1 and 2 and building the connection between stations 2 and 4 instead. The curvature of the rails does not matter because you have a hammer.

In the second case, drawn in Figure E.2, connecting all three stations is not possible.

Figure E.1: the first sample input.

Figure E.2: the second sample input.