#include <fstream>

using namespace std;

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

const int nmax = 50005 , mmax = 250005 , INFINIT = 2000000000;

int n,m,x,y,c;

struct costuri{
int x,y,c;
}costs[mmax];

void quickSortByX(costuri costs[], int left, int right){
int i = left, j = right;
int aux,aux2,aux3;
int pivot = costs[(i + j)/2].x;

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

    if(i <= j){
        aux=costs[i].x;
        aux2=costs[i].y;
        aux3=costs[i].c;
        costs[i].x=costs[j].x;
        costs[i].y=costs[j].y;
        costs[i].c=costs[j].c;
        costs[j].x=aux;
        costs[j].y=aux2;
        costs[j].c=aux3;

        i++;
        j--;
    }
};
if(left<j)quickSortByX(costs,left,j);
if(i<right)quickSortByX(costs,i,right);
}

int binarySearch(costuri costs[], int value, int left, int right){
while(left<=right){
     int middle = (left + right)/2;
     if(costs[middle].x == value)return middle;
     else if (costs[middle].x > value)right = middle -1;
     else left = middle +1;
}
return -1;
}

void dijkstra(int x){
    int i,minim,k,poz,poz2;
    bool viz[nmax];
    int d[nmax];

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

    for(i = 1;i<=m ; i++){
        if(costs[i].x==x)d[costs[i].y]=costs[i].c;
        else break;
    }

    viz[x]=1;
    d[x]=0;
    int ok = 1;

    while(ok){
        minim = INFINIT;
        for(i=1;i<=n;i++)
        if(viz[i]==0&&d[i]<minim){
            minim=d[i];
            k=i;
        }
        if(minim!=INFINIT){
            viz[k]=1;
            poz = binarySearch(costs, k ,1,m);
            if(poz!=-1){
                poz2=poz+1;
                while(costs[poz].x==k){
                    if(viz[costs[poz].y]==0&&d[costs[poz].y]>d[k]+costs[poz].c) d[costs[poz].y]=d[k]+costs[poz].c;
                    poz--;
                }
                while(costs[poz2].x==k){
                    if(viz[costs[poz2].y]==0&&d[costs[poz2].y]>d[k]+costs[poz2].c) d[costs[poz2].y]=d[k]+costs[poz2].c;
                    poz2++;
                }
            }
            }
        else ok = 0;
        }
        for(i=2;i<=n;i++){
            if(d[i]!=INFINIT)g<<d[i]<<" ";
            else g<<0<<" ";
        }
    }

int main()
{

    f >> n >> m;

    for(int i = 1; i <= m; i++){
        f >> x >> y >> c;
        costs[i].x = x;
        costs[i].y = y;
        costs[i].c = c;
    }

    quickSortByX(costs,1,m);

    dijkstra(1);

    g<<'\n';

    return 0;
}