package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
)

const INF = 1000000000

type Edge struct {
	to     int
	rev    int
	cap    int
	flow   int
	cost   int
	origID int
}

type OrigEdge struct {
	u, v, c, w int
}

type Item struct {
	vertex   int
	priority int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}
func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(*Item))
}
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n, m int
	if _, err := fmt.Fscan(reader, &n, &m); err != nil {
		return
	}

	edges := make([]OrigEdge, m)
	for i := 0; i < m; i++ {
		fmt.Fscan(reader, &edges[i].u, &edges[i].v, &edges[i].c, &edges[i].w)
	}

	nNodes := n + 2
	S := 0
	T := n + 1
	graph := make([][]Edge, nNodes)
	bal := make([]int, nNodes)

	addEdge := func(u, v, cap, cost, origID int) {
		graph[u] = append(graph[u], Edge{v, len(graph[v]), cap, 0, cost, origID})
		graph[v] = append(graph[v], Edge{u, len(graph[u]) - 1, 0, 0, -cost, -1})
	}

	for i := 0; i < m; i++ {
		u, v, c, w := edges[i].u, edges[i].v, edges[i].c, edges[i].w
		r := c % 2
		bal[u] -= r
		bal[v] += r
		C := c / 2
		W := 2 * w
		if W < 0 {
			bal[u] -= 2 * C
			bal[v] += 2 * C
			addEdge(v, u, C, -W, i)
		} else {
			addEdge(u, v, C, W, i)
		}
	}

	if bal[1]%2 != 0 {
		bal[1] += 1
		bal[n] -= 1
	}
	addEdge(n, 1, INF, 0, -1)

	sumReq := 0
	for i := 1; i <= n; i++ {
		if bal[i]%2 != 0 {
			fmt.Println("Impossible")
			return
		}
		req := bal[i] / 2
		if req > 0 {
			addEdge(S, i, req, 0, -1)
			sumReq += req
		} else if req < 0 {
			addEdge(i, T, -req, 0, -1)
		}
	}

	flow := 0
	pot := make([]int, nNodes)

	for {
		dist := make([]int, nNodes)
		for i := range dist {
			dist[i] = INF
		}
		parentEdge := make([]int, nNodes)
		parentVertex := make([]int, nNodes)
		for i := range parentEdge {
			parentEdge[i] = -1
			parentVertex[i] = -1
		}

		dist[S] = 0
		pq := PriorityQueue{}
		heap.Push(&pq, &Item{vertex: S, priority: 0})

		for pq.Len() > 0 {
			curr := heap.Pop(&pq).(*Item)
			u := curr.vertex
			if curr.priority > dist[u] {
				continue
			}

			for i, e := range graph[u] {
				if e.cap > e.flow {
					newDist := dist[u] + e.cost + pot[u] - pot[e.to]
					if newDist < dist[e.to] {
						dist[e.to] = newDist
						parentVertex[e.to] = u
						parentEdge[e.to] = i
						heap.Push(&pq, &Item{vertex: e.to, priority: newDist})
					}
				}
			}
		}

		if dist[T] == INF {
			break
		}

		for i := 0; i < nNodes; i++ {
			if dist[i] != INF {
				pot[i] += dist[i]
			}
		}

		push := INF
		curr := T
		for curr != S {
			p := parentVertex[curr]
			idx := parentEdge[curr]
			rem := graph[p][idx].cap - graph[p][idx].flow
			if rem < push {
				push = rem
			}
			curr = p
		}

		flow += push
		curr = T
		for curr != S {
			p := parentVertex[curr]
			idx := parentEdge[curr]
			rev := graph[p][idx].rev
			graph[p][idx].flow += push
			graph[curr][rev].flow -= push
			curr = p
		}
	}

	if flow < sumReq {
		fmt.Println("Impossible")
		return
	}

	fmt.Println("Possible")
	ans := make([]int, m)
	for u := 0; u < nNodes; u++ {
		for _, e := range graph[u] {
			if e.origID != -1 {
				id := e.origID
				origC := edges[id].c
				origW := edges[id].w
				r := origC % 2
				C := origC / 2

				if origW < 0 {
					ans[id] = r + 2*(C-e.flow)
				} else {
					ans[id] = r + 2*e.flow
				}
			}
		}
	}

	for i := 0; i < m; i++ {
		if i > 0 {
			fmt.Print(" ")
		}
		fmt.Print(ans[i])
	}
	fmt.Println()
}