We show that for those lattices of Voronoi's first kind, a vector of shortest nonzero Euclidean length can computed in polynomial time by computing a minimum cut in a graph.