{-# LANGUAGE Strict #-}

import Data.ByteString.Char8 qualified as B
import Data.IntMap.Strict qualified as M
import Control.Monad
import Data.List
import Data.Graph
import Data.Array.Unboxed
import Data.Array.ST
import Control.Monad.ST
import Control.Monad.Trans.Maybe
import Control.Monad.Trans
import Data.Foldable

data UnionFind s
 = UnionFind
 { pa :: STUArray s Int Int
 , sz :: STUArray s Int Int
 }
mkUnionFind :: Int -> ST s (UnionFind s)
mkUnionFind n = UnionFind
 <$> newListArray (1,n) [1..n]
 <*> newArray (1,n) 1
ufind uf i = do
 p <- readArray (pa uf) i
 if p == i
    then pure i
    else ufind uf p >>= \p' -> p' <$ writeArray (pa uf) i p'
uunion uf i' j' = bothM (ufind uf) (i',j') >>= \(i,j) -> when (i /= j) $ do
 readArray (sz uf) i >>= modifyArray' (sz uf) j . (+)
 writeArray (pa uf) i j

int = (\(Just (x,_)) -> x) . B.readInt
intl = map int . B.words <$> B.getLine

ranks :: STUArray s Int Int -> [Int] -> ST s (Int -> ST s Int, Int -> Int, Int)
ranks a xs = do
  forM_ xs $ \i -> writeArray a i 0
  (n, order) <- foldM (\(c,acc) i -> do
    o <- readArray a i
    if o == 0
       then (c + 1, (c, i) : acc) <$ writeArray a i c
       else pure (c, acc))
    (1,[])
    xs
  let invRank :: UArray Int Int = array (1, n - 1) order
  pure (readArray a, (invRank !), n - 1)

twoColour :: Graph -> Maybe [([Int], [Int])]
twoColour g
  | any (\(u,v) -> (colours!u) == (colours!v)) (edges g) = Nothing
  | otherwise = Just $ partition ((>0) . (colours!)) . toList <$> comps
 where
  (1, n) = bounds g
  comps = dff g
  colours :: UArray Int Int = runSTUArray $ do
    col <- newArray (1, n) (-1)
    let colour c (Node i ch) = writeArray col i c >> mapM_ (colour (1 - c)) ch
    col <$ mapM_ (colour 0) comps

bothM f (a,b) = (,) <$> f a <*> f b

solve :: Int -> [[(Int, Int)]] -> MaybeT (ST s) Int
solve n evs = do
 uf <- lift (mkUnionFind n)
 rankA <- lift (newArray (1,n) 0)
 fmap sum $ forM evs $ \ev -> do
  ev <- lift $ forM ev $ bothM (ufind uf)
  when (any (uncurry (==)) ev) $ fail "contradiction"
  (rank, invRank, n) <- lift (ranks rankA $ concatMap (\(u,v) -> [u,v]) ev)
  g <- lift $ buildG (1,n) . concat <$> forM ev (fmap (\(u,v) -> [(u,v), (v,u)]) . bothM rank)
  colourClasses <- hoistMaybe $ twoColour g
  res <- lift $ sum . map (uncurry min) <$> forM colourClasses (bothM (fmap sum . mapM (readArray (sz uf) . invRank)))
  lift $ forM_ ev $ uncurry (uunion uf)
  pure res


main = do
 [n,m] <- intl
 events :: M.IntMap [(Int,Int)] <- foldl' (\m [u,v,t] -> M.alter (Just . maybe [(u,v)] ((u,v):)) t m) M.empty
   <$> replicateM m intl
 putStrLn $ maybe "impossible" (("possible\n"++) . show) $ runST $ runMaybeT $ solve n $ reverse $ M.elems events