#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,p,a,b,m,mat[25005][25005],f[25005],d[25005],val,vmin;
queue<int>q;
int main()
{
    fin>>n>>p;
    for(int i=1;i<=p;i++)
    {
        fin>>a>>b>>m;
        mat[a][b]=m;
    }
    f[1]=1;
    for(int i=1;i<=n;i++)
    {
        if(mat[1][i]!=0)
        {
            d[i]=mat[1][i];
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(d[i]==0){d[i]=1e9;}
    }
    d[1]=0;
    q.push(1);
    while(!q.empty())
    {
        vmin=1e9;
        val=-1;
        for(int i=1;i<=n;i++)
        {
            if(f[i]==0&&d[i]<vmin)
            {
                vmin=d[i];
                val=i;
            }
        }
        if(val==-1){break;}
        q.push(val);
        f[val]=1;
        for(int i=1;i<=n;i++)
        {
            if(mat[val][i]!=0 && f[i]==0)
            {
                d[i]=min(d[i],d[val]+mat[val][i]);
            }
        }
        q.pop();
    }
    for(int i=2;i<=n;i++)
    {
        if(d[i]!=1e9){fout<<d[i]<<" ";}
        else{fout<<0<<" ";}
    }
    fin.close();
    fout.close();
    return 0;
}