#include <iostream>
#include <fstream>
#include <list>
#include <queue>

using namespace std;

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

int n,m;

list <int> adj[50005];
list <int> cost[50005];
queue <int> coada;
int dist[50005];
bool incoada[50005];

void bell(int source)

{

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

        dist[i]=1<<30;

    dist[source]=0;

    coada.push(source);

    incoada[source]=1;



    while(!coada.empty())
    {

        int nc=coada.front();

        incoada[nc]=0;

        coada.pop();

        list <int> :: iterator i,j;

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

        {

            int u=*i;

            int cat=*j;

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

            {

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

                if(!incoada[u])

                {

                    coada.push(u);

                    incoada[u]=1;

                }

            }



        }

    }

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

}



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);

    }
    bell(1);
    return 0;

}