local mma = math.max
local AvlTree = {}
AvlTree.makenode = function(self, val, parent)
  local node = {}
  node.v, node.lc, node.rc = val, 0, 0
  node.p = parent
  -- node.l, node.r = nil, nil
  return node
end
AvlTree.create = function(self, lessthan)
  self.lessthan = lessthan
end

AvlTree.recalcCount = function(self, node)
  if node then
    if node.l then node.lc = 1 + mma(node.l.lc, node.l.rc)
    else node.lc = 0
    end
    if node.r then node.rc = 1 + mma(node.r.lc, node.r.rc)
    else node.rc = 0
    end
  end
end
AvlTree.recalcCountAll = function(self, node)
  while node do
    self:recalcCount(node)
    node = node.p
  end
end

AvlTree.rotR = function(self, child, parent)
  local granp = parent.p
  child.r, parent.l = parent, child.r
  child.p, parent.p = granp, child
  if parent.l then parent.l.p = parent end
  if granp then
    if granp.l == parent then
      granp.l = child
    else
      granp.r = child
    end
  else -- granp == nil
    self.root = child
  end
  self:recalcCountAll(parent)
end

AvlTree.rotL = function(self, child, parent)
  local granp = parent.p
  child.l, parent.r = parent, child.l
  child.p, parent.p = granp, child
  if parent.r then parent.r.p = parent end
  if granp then
    if granp.r == parent then
      granp.r = child
    else
      granp.l = child
    end
  else -- granp == nil
    self.root = child
  end
  self:recalcCountAll(parent)
end

AvlTree.add = function(self, val)
  if not self.root then self.root = self:makenode(val) return end
  local pos = self.root
  local added = false
  while not added do
    if self.lessthan(val, pos.v) then
      if pos.l then
        pos = pos.l
      else
        pos.l = self:makenode(val, pos)
        pos = pos.l
        added = true
      end
    else
      if pos.r then
        pos = pos.r
      else
        pos.r = self:makenode(val, pos)
        pos = pos.r
        added = true
      end
    end
  end
  self:recalcCountAll(pos)
  local resolve_child = pos
  while resolve_child do
    local child, parent = resolve_child, resolve_child.p
    resolve_child = nil
    if not parent then
      break
    end
    if parent.l == child then
      if parent.lc - 1 == parent.rc then
        resolve_child = parent
      elseif parent.lc - 2 == parent.rc then
        if child.lc - 1 == child.rc then
          self:rotR(child, parent)
        else
          local cr = child.r
          self:rotL(cr, child)
          self:rotR(cr, parent)
        end
      end
    else -- parent.r == child
      if parent.rc - 1 == parent.lc then
        resolve_child = parent
      elseif parent.rc - 2 == parent.lc then
        if child.rc - 1 == child.lc then
          self:rotL(child, parent)
        else
          local cl = child.l
          self:rotR(cl, child)
          self:rotL(cl, parent)
        end
      end
    end
  end
end

AvlTree.rmsub = function(self, node)
  while node do
    self:recalcCount(node)
    if node.lc == node.rc then
      node = node.p
    elseif node.lc + 1 == node.rc then
      self:recalcCountAll(node.p)
      node = nil
    else
      if node.r.lc == node.r.rc then
        self:rotL(node.r, node)
        self:recalcCountAll(node)
        node = nil
      elseif node.r.lc + 1 == node.r.rc then
        local nr = node.r
        self:rotL(nr, node)
        node = nr
      else
        local nrl = node.r.l
        self:rotR(nrl, node.r)
        self:rotL(nrl, node)
        node = nrl
      end
    end
  end
end

AvlTree.pop = function(self)
  local edge = self.root
  while edge.l do
    edge = edge.l
  end
  local v = edge.v
  if edge.p then
    if edge.r then edge.r.p = edge.p end
    edge.p.l = edge.r
    self:rmsub(edge.p)
  else
    if edge.r then edge.r.p = nil end
    self.root = edge.r
  end
  return v
end

AvlTree.new = function(lessthan)
    local obj = {}
    setmetatable(obj, {__index = AvlTree})
    obj:create(lessthan)
    return obj
end


local n, m = io.read("*n", "*n")
local ps, qs, cs = {}, {}, {}
local companies = {}
local stations = {}
for i = 1, n do
  stations[i] = {}
end
for i = 1, m do
  local p, q, c = io.read("*n", "*n", "*n")
  if not companies[c] then companies[c] = {} end
  if stations[p][c] and stations[q][c] then
    if stations[p][c] ~= stations[q][c] then
      local ci_p, ci_q = stations[p][c], stations[q][c]
      if #companies[c][ci_p] < #companies[c][ci_q] then
        for j = 1, #companies[c][ci_p] do
          local st = companies[c][ci_p][j]
          stations[st][c] = ci_q
          table.insert(companies[c][ci_q], st)
        end
        companies[c][ci_p] = {}
      else
        for j = 1, #companies[c][ci_q] do
          local st = companies[c][ci_q][j]
          stations[st][c] = ci_p
          table.insert(companies[c][ci_p], st)
        end
        companies[c][ci_q] = {}
      end
    end
  elseif not stations[p][c] and not stations[q][c] then
    table.insert(companies[c], {p, q})
    stations[p][c] = #companies[c]
    stations[q][c] = #companies[c]
  elseif stations[p][c] then
    local idx = stations[p][c]
    stations[q][c] = idx
    table.insert(companies[c][idx], q)
  else
    local idx = stations[q][c]
    stations[p][c] = idx
    table.insert(companies[c][idx], p)
  end
end
local len = {}
local tasknum = 0
local done = 0
local tasktree = AvlTree.new(function(x, y) return len[x[1]][x[2]] < len[y[1]][y[2]] end)
for company, groups in pairs(companies) do
  len[company] = {}
  for i = 1, #groups do
    len[company][i] = -1
  end
end
local function addtask(company, group)
  tasknum = tasknum + 1
  tasktree:add({company, group})
end
for company, group in pairs(stations[1]) do
  len[company][group] = 1
  addtask(company, group)
end
while done < tasknum do
  done = done + 1
  local taskidx = tasktree:pop()
  local src_company, src_group =taskidx[1], taskidx[2]
  local srclen = len[src_company][src_group]
  for i = 1, #companies[src_company][src_group] do
    local station = companies[src_company][src_group][i]
    for dst_company, dst_group in pairs(stations[station]) do
      if src_company ~= dst_company then
        local dstlen = len[dst_company][dst_group]
        if dstlen == -1 or srclen + 1 < dstlen then
          len[dst_company][dst_group] = srclen + 1
          addtask(dst_company, dst_group)
        end
      end
    end
  end
end
local ret = -1
local mmi = math.min
for company, group in pairs(stations[n]) do
  local dstlen = len[company][group]
  if 0 < dstlen then
    if ret == -1 then
      ret = dstlen
    else
      ret = mmi(ret, dstlen)
    end
  end
end
print(ret)
