#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 quickSortByCost(costuri vecini[], int x, int left, int right){
int i = left,j = right;
int aux,aux2;
int pivot = vecini[x].c[(i+j)/2];

while(i<=j){
    while(vecini[x].c[i]<pivot)i++;
    while(vecini[x].c[j]>pivot)j--;

    if(i<=j){
        aux=vecini[x].c[i];
        aux2=vecini[x].v[i];
        vecini[x].c[i]=vecini[x].c[j];
        vecini[x].v[i]=vecini[x].v[j];
        vecini[x].c[j]=aux;
        vecini[x].v[j]=aux2;
        i++;
        j--;
    }
};
if(left<j)quickSortByCost(vecini,x,left,j);
if(i<right)quickSortByCost(vecini,x,i,right);
}


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);
    }

    for(int i=1;i<=n;i++)
        quickSortByCost(vecini,i,0,vecini[i].c.size()-1);

    dijkstra(1,vecini);

    g<<'\n';

    return 0;
}