package main

import (
	"bufio"
	"fmt"
	"os"
	"sync"

	"github.com/emirpasic/gods/lists/arraylist"
	"github.com/emirpasic/gods/sets/hashset"
	"github.com/emirpasic/gods/trees/binaryheap"
)

var nodeDetaMap map[int64]*arraylist.List
var edgeDagaMap map[string]int64

type SearchData struct {
	Path *arraylist.List
	Cost int64
}

func main() {
	r := bufio.NewReader(os.Stdin)
	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()

	var n, m int64
	fmt.Fscan(r, &n, &m)

	nodeDetaMap = map[int64]*arraylist.List{}
	for i := int64(0); i < n; i++ {
		nodeData := arraylist.New()
		nodeDetaMap[i+1] = nodeData
	}

	var a, b, c int64
	edgeDagaMap = map[string]int64{}
	for i := int64(0); i < m; i++ {
		fmt.Fscan(r, &a, &b, &c)

		nodeData := nodeDetaMap[a]
		nodeData.Add(b)
		nodeDetaMap[a] = nodeData
		nodeData, _ = nodeDetaMap[b]
		nodeData.Add(a)
		nodeDetaMap[b] = nodeData

		key := genKeyForEdgeData(a, b)
		edgeDagaMap[key] = c
	}

	usedEdgeMap := hashset.New()
	var wg sync.WaitGroup
	var lock sync.Mutex

	for i := int64(1); i <= n; i++ {
		for j := i + 1; j <= n; j++ {
			wg.Add(1)
			go func(gi, gj int64) {
				usedKeys := searchRoute(gi, gj)
				lock.Lock()
				for _, key := range usedKeys {
					usedEdgeMap.Add(key)
				}
				lock.Unlock()
				wg.Done()
			}(i, j)
		}
	}

	wg.Wait()

	result := len(edgeDagaMap) - usedEdgeMap.Size()
	fmt.Fprintln(w, result)
}

func genKeyForEdgeData(a int64, b int64) string {
	if a > b {
		a, b = b, a
	}

	return fmt.Sprintf("%d#%d", a, b)
}

func searchRoute(start int64, end int64) (usedKeys []string) {
	base := &SearchData{}
	base.Path = arraylist.New()
	base.Path.Add(start)
	base.Cost = 0

	comparator := func(a, b interface{}) int {
		aAsserted := a.(*SearchData)
		bAsserted := b.(*SearchData)
		switch {
		case aAsserted.Cost > bAsserted.Cost:
			return 1
		case aAsserted.Cost < bAsserted.Cost:
			return -1
		default:
			return 0
		}
	}

	heap := binaryheap.NewWith(comparator)
	heap.Push(base)

	var bestRoute *SearchData
	for heap.Size() != 0 {
		t, _ := heap.Pop()
		tmp := t.(*SearchData)

		l, _ := tmp.Path.Get(tmp.Path.Size() - 1)
		last := l.(int64)
		if last == end {
			bestRoute = tmp
			break
		}

		nextList := nodeDetaMap[last]
		it := nextList.Iterator()
		for it.Next() {
			next := it.Value().(int64)
			if tmp.Path.Contains(next) {
				continue
			}

			newSearcnData := &SearchData{}
			newSearcnData.Path = arraylist.New()
			tmpIt := tmp.Path.Iterator()
			for tmpIt.Next() {
				newSearcnData.Path.Add(tmpIt.Value())
			}
			newSearcnData.Path.Add(next)

			key := genKeyForEdgeData(last, next)
			cost := edgeDagaMap[key]
			newSearcnData.Cost = tmp.Cost + cost
			heap.Push(newSearcnData)
		}
	}

	var tmp, next int64
	t, _ := bestRoute.Path.Get(0)
	tmp = t.(int64)
	for i := 0; i < bestRoute.Path.Size()-1; i++ {
		n, _ := bestRoute.Path.Get(i + 1)
		next = n.(int64)

		key := genKeyForEdgeData(tmp, next)
		usedKeys = append(usedKeys, key)
		tmp = next
	}

	return usedKeys
}
