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

void dijkstra(int x,costuri costs[]){
    int i,minim,k;
    bool viz[n];
    int d[n];

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

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

    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;

            for(i=0;i<costs[k].v.size();i++)
                if(d[costs[k].v[i]]>d[k]+costs[k].c[i]&&viz[costs[k].v[i]]==0)
                    d[costs[k].v[i]] = d[k] + costs[k].c[i];

            }
        else ok = 0;
        }
        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 costs[nmax];
    for(int i = 1; i <= m; i++){
        f >> x >> y >> c;
        costs[x].v.push_back(y);
        costs[x].c.push_back(c);
    }

    dijkstra(1,costs);

    g<<'\n';

    return 0;
}