import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List
import Data.Array
import Control.Monad

main = do
  li <- BS.getLine
  let [n,q] = unfoldr (BS.readInt . BS.dropWhile isSpace) li
  abs <- forM [2..n] get2
  pxs <- forM [1..q] get2
  let ans = compute n q abs pxs
  putStrLn $ unwords $ map show ans

get2 _ = do
  li <- BS.getLine
  let [a,b] = unfoldr (BS.readInt . BS.dropWhile isSpace) li
  return (a,b)

compute :: Int -> Int -> [(Int,Int)] -> [(Int,Int)] -> [Int]
compute n _ abs pxs = ans
  where
    xa = accumArray (+) 0 (1,n) pxs
    tmx = accumArray (||) False ((1,1),(n,n)) [ (p,True) | (a,b) <- abs, p <- [(a,b),(b,a)] ]
    gett q p = [ i | 1 <= p, p <= n, i <- [1..n], tmx ! (p,i), i /= q ]
    ans = xa ! 1 : (map snd $ sort $ concatMap (dfs 1 (xa!1)) (gett 0 1))
    dfs p v cur = (cur, v1) : concatMap (dfs cur v1) (gett p cur)
      where
        v1 = v + xa ! cur