#include <fstream>
#include <vector>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int INFINIT = 2000000000;

int n,m,x,y,c;

struct costuri{
vector<int>v,c;
};

vector<int>nod;
void dijkstra(int x,costuri vecini[]){
    int i,j;
    bool viz[n];
    int d[n];

    for(i=1; i <=n;i++)
    {
        d[i]=INFINIT;
        viz[i]=0;
    }

    for(i=0;i<vecini[x].v.size();i++){
        d[vecini[x].v[i]]=vecini[x].c[i];
    }

    viz[x]=1;
    d[x]=0;
    nod.push_back(x);

    for(i=0;i<nod.size();i++){
        for(j=0;j<vecini[nod[i]].v.size();j++){
        if(viz[vecini[nod[i]].v[j]]==0){
                nod.push_back(vecini[nod[i]].v[j]);
        viz[vecini[nod[i]].v[j]]=1;}
            if(d[vecini[nod[i]].v[j]]>d[nod[i]]+vecini[nod[i]].c[j]){
                d[vecini[nod[i]].v[j]] = d[nod[i]]+vecini[nod[i]].c[j];
            }
        }
    }
        for(i=2;i<=n;i++){
            if(d[i]!=INFINIT)g<<d[i]<<" ";
            else g<<0<<" ";
        }
    }

int main()
{


    f >> n >> m;
    const int nmax = n+1;
    costuri vecini[nmax];
    for(int i = 1; i <= m; i++){
        f >> x >> y >> c;
        vecini[x].v.push_back(y);
        vecini[x].c.push_back(c);
    }

    dijkstra(1,vecini);

    g<<'\n';

    return 0;
}