#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

int N,M;
bool in[50001];
int nrq[50001];

struct edge
{
    int next,cost;
};

edge aux;
vector <edge> g[50001];
queue <int> Q;
int best[50001];

int main()
{
    freopen ("bellmanford.in","r",stdin);
    freopen ("bellmanford.out","w",stdout);

    scanf ("%d %d",&N,&M);
    int i,x,y,c;

    for (i=1; i<=M; i++)
    {
        scanf ("%d %d %d",&x,&y,&c);
        aux.next=x;
        aux.cost=c;
        g[y].push_back(aux);
        aux.next=y;
        g[x].push_back(aux);
    }

    int S=1;
    Q.push(S);
    in[S]=1;
    best[S]=0;
    nrq[S]++;

    int j,node;
    while (!Q.empty())
    {
        node=Q.front();
        Q.pop();
        in[node]=false;
        for (j=0; j<g[node].size(); j++)
        {
            if (best[g[node][j].next]>best[node]+g[node][j].cost)
            {
                best[g[node][j].next]=best[node]+g[node][j].cost;
                if (in[g[node][j].next]==false)
                {
                    Q.push(g[node][j].next);
                    in[g[node][j].next]=true;
                    nrq[g[node][j].next]++;
                }
            }
        }
    }

    return 0;
}