#include <iostream>

#include <fstream>

#include <list>



using namespace std;



ifstream f("dijkstra.in");

ofstream g("dijkstra.out");



const int inf=1<<30;



list <int> adj[55555];

list <int> cost[55555];

int n,m;

int dist[55555];

bool viz[55555];



int distmin()

{

    int k=50505;

    dist[k]=inf;

    for(int i=1;i<=n;++i)

        if(dist[i]<dist[k] and !viz[i])

            k=i;

    return k;

}



void dijkstra()

{

    for(int i=1;i<=n;++i)

        dist[i]=inf;

    dist[1]=0;

    for(int i=1;i<=n-1;++i)

    {

        int nc=distmin();

        viz[nc]=1;

        list <int> :: iterator it,jt;

        for(it=adj[nc].begin(),jt=cost[nc].begin();it!=adj[nc].end();++it,++jt)

        {

            int v=*it;

            int cat=*jt;

            if(dist[v]>dist[nc]+cat)

                dist[v]=dist[nc]+cat;

        }

    }

}



int main()

{

    f>>n>>m;

    for(int i=1;i<=m;++i)

    {

        int a,b,c;

        f>>a>>b>>c;

        adj[a].push_back(b);

        cost[a].push_back(c);

    }

    dijkstra();

    for(int i=2;i<=n;++i)
       if(dist[i]!=inf)
       g<<dist[i]<<' ';
       else g<<0<<' ';

    return 0;

}