#include <iostream>
#include <vector>
#include <set>
#include <list>
#include <fstream>
using namespace std;
vector <int> d,viz;///distanta
vector <list<pair<int,int>>> L;
set <pair<int,int>> Q;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int main()
{
    int n,m,i,a,b,c;
    f>>n>>m;///numarul de noduri si lista de muchii
    L.resize(n+1);
    d.resize(n+1);
    for(i=0; i<m; i++)
    {
        f>>a>>b>>c;
        L[a].push_back({c,b});
    }
    for(i=1; i<=n; i++)
        viz.push_back(0);cout<<viz.size();
    d[1]=0;
    for(i=2; i<=n; i++)
        d[i]=9999999;
    Q.insert({0,1});
    while(!Q.empty())
    {
        int nod=Q.begin()->second;
        Q.erase(Q.begin());
        if(!viz[nod])
        {

            viz[nod]=1;
            for(list<pair<int,int>> ::iterator u=L[nod].begin(); u!=L[nod].end(); u++)
            {
                if(d[nod]+u->first<d[u->second])
                {
                    d[u->second]=d[nod]+u->first;
                    Q.insert({d[u->second],u->second});
                }
            }
        }
    }
    //cout<<"Distanta ce mai scurta din nodul 1 la celelalte noduri";
    for(i=2; i<=n; i++)
        if(d[i]!=9999999)
            g<<d[i]<<" ";
        else
            g<<0<<" ";///practic nu exista

}