Consider a directed graph G with distinct and nonnegative edge lengths.

Lets be a starting vertex and t a destination vertex, and assume that G has at least one st path. Which of the following statements are true? (Choose all that apply.)

1. The shortest (meaning minimum-length) s-t path might have as many as n - 1 edges, where n is the number of vertices.
2. There is a shortest s-t path with no repeated vertices (that is, with no loops).
3. The shortest s-t path must include the minimum-length edge of G.
4. The shortest s-t path must exclude the maximum-length edge of G.