# Shortest Path in a Directed Acyclic Graph
## Problem Statement
You are given a Directed Acyclic Graph (DAG) with $N$ vertices, labeled from $0$ to $N-1$, and $M$ directed edges. Each edge connects two vertices and has an associated weight. The graph is provided as a list of edges, where each edge is represented by three integers: a source vertex $u$, a destination vertex $v$, and a weight $w$. This means there is a directed edge from $u$ to $v$ with a distance (weight) of $w$.
Your task is to find the shortest path from a designated source vertex (vertex $0$) to all other vertices in the graph. For any vertex that is unreachable from vertex $0$, its shortest path distance should be reported as $-1$.
## Input Format
- The first line contains two space-separated integers, $N$ and $M$, representing the number of vertices and the number of edges, respectively.
- $1 \le N \le 5 \cdot 10^4$
- $1 \le M \le 5 \cdot 10^4$
- The next $M$ lines each describe an edge. Each line contains three space-separated integers: $u, v, w$.
- $0 \le u, v < N$
- $1 \le w \le 10^4$
## Output Format
Output a single line containing $N$ space-separated integers. The $i$-th integer (0-indexed) should be the shortest distance from vertex $0$ to vertex $i$. If vertex $i$ is unreachable from vertex $0$, output $-1$ for that vertex.
## Sample Test Cases
### Sample Input 1
```
4 2
0 1 2
0 2 1
```
### Sample Output 1
```
0 2 1 -1
```
### Sample Input 2
```
6 7
0 1 2
0 4 1
4 5 4
4 2 2
1 2 3
2 3 6
5 3 1
```
### Sample Output 2
```
0 2 3 6 1 5
```
## Constraints
- $1 \le N, M \le 5 \cdot 10^4$
- $0 \le u, v < N$
- $1 \le w \le 10^4$
- The graph is guaranteed to be a Directed Acyclic Graph (DAG).
- Time limit: 1 second
- Memory limit: 256 MB
## Explanation
### Sample 1:
- $N=4, M=2$
- Edges: $(0,1,2)$, $(0,2,1)$
- Shortest path from $0$ to $0$: $0$.
- Shortest path from $0$ to $1$: $0 \to 1$ with weight $2$.
- Shortest path from $0$ to $2$: $0 \to 2$ with weight $1$.
- Vertex $3$ is unreachable from $0$, so its distance is $-1$.
### Sample 2:
- $N=6, M=7$
- Edges: $(0,1,2)$, $(0,4,1)$, $(4,5,4)$, $(4,2,2)$, $(1,2,3)$, $(2,3,6)$, $(5,3,1)$
- Shortest path from $0$ to $0$: $0$.
- Shortest path from $0$ to $1$: $0 \to 1$ with weight $2$.
- Shortest path from $0$ to $2$: $0 \to 4 \to 2$ with total weight $1+2=3$. (Note: $0 \to 1 \to 2$ would be $2+3=5$, which is longer).
- Shortest path from $0$ to $3$: $0 \to 4 \to 5 \to 3$ with total weight $1+4+1=6$. (Note: $0 \to 1 \to 2 \to 3$ would be $2+3+6=11$, and $0 \to 4 \to 2 \to 3$ would be $1+2+6=9$, both longer).
- Shortest path from $0$ to $4$: $0 \to 4$ with weight $1$.
- Shortest path from $0$ to $5$: $0 \to 4 \to 5$ with total weight $1+4=5$.
Loading problem statement...