\begin{tikzpicture}[
  scale=1.1,
  graph vertex/.style={draw, circle, minimum size=0.55cm, inner sep =0pt},
  edge label/.style={inner sep=0pt, circle, fill=white}
]
\node[graph vertex] (v1) at (.50, 5.00) {1};
\node[graph vertex, toilet] (v2) at (2.50, 5.00) {2};
\node[graph vertex] (v3) at (5.00, 5.00) {3};
\node[graph vertex] (v4) at (4.00, 4.15) {4};
\node[graph vertex] (v5) at (1.00, 3.50) {5};
\node[graph vertex] (v6) at (5.50, 3.50) {6};
\node[graph vertex] (v7) at (2.80, 3.00) {7};
\node[graph vertex] (v8) at (1.40, 2.25) {8};
\node[graph vertex] (v9) at (4.00, 2.55) {9};
\node[graph vertex] (v10) at (5.50, 2.20) {10};
\node[graph vertex] (v11) at (2.90, 1.50) {11};
\node[graph vertex] (v12) at (4.20, 1.1) {12};
\node[graph vertex, start] (v13) at (5.50, .80) {13};
\node[graph vertex, toilet] (v14) at (1.00, .80) {14};
\node[graph vertex] (v15) at (2.80, .10) {15};
\node[graph vertex] (v16) at (4.50, .07) {16};

\graph[edge quotes mid] {
  (v1) --["9" edge label] (v2),
  (v2) --["6" edge label] (v4),
  (v3) --["3" edge label] (v6),
  (v3) --["2" edge label] (v4),
  (v4) --["4" edge label] (v9),
  (v2) --["4" edge label] (v7),
  (v7) --["5" edge label] (v9),
  (v9) --["5" edge label] (v6),
  (v7) --["6" edge label] (v11),
  (v9) --["8" edge label] (v11),
  (v9) --["5" edge label] (v10),
  (v10) --["9" edge label] (v11),
  (v11) --["5" edge label] (v12),
  (v12) --["4" edge label] (v13),
  (v13) --["7" edge label] (v16),
  (v16) --["3" edge label] (v15),
  (v8) --["5" edge label] (v11),
  (v5) --["5" edge label] (v8),
  (v8) --["8" edge label] (v14),
  (v14) --["15" edge label, bend left] (v5),
  (v4) --["7" edge label] (v6),
  (v11) --["5" edge label] (v15),
  (v10) --["5" edge label] (v13),
  (v6) --["6" edge label] (v10)
};
\end{tikzpicture}