#include<fstream>
#define nr 3000
using namespace std;
int maxi=10000;
int a[nr][nr],mini,d[nr],c;
int i,n,m,poz,j,s[nr];
int main()
{ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
f>>n>>m;
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        if(i==j) a[i][j]=0;
    else a[i][j]=maxi;
        while(f>>i>>j>>c)
    a[i][j]=c;
        s[1]=1;
        d[1]=a[1][1];
        for(i=2;i<=n;i++)
            d[i]=a[1][i];
            for(i=1;i<n;i++)
        {mini=maxi;
        for(j=1;j<=n;j++)
            if(s[j]==0)
                if(d[j]<mini)
                {mini=d[j];
                poz=j;}
                s[poz]=1;

    for(j=1;j<=n;j++)
        if(s[j]==0)
            if(d[j]>d[poz]+a[poz][j])
            {d[j]=d[poz]+a[poz][j];}}
        for(i=2;i<=n;i++)
            if (d[i]==maxi) g<<0<<" ";
else g<<d[i]<<" ";}