#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

struct edge
{
    int next,cost;
};

class compare
{
public:
    bool operator () (edge &x,edge &y)
    {
        return x.cost>y.cost;
    }
} ;

vector <edge> v[50001];

priority_queue <edge, vector<edge>, compare> H;

int dist[50001];
bool viz[50001];

void Dijkstra (int S)
{
    dist[S]=0;
    int K,j;
    edge E;
    E.next=S;
    E.cost=dist[S];
    H.push(E);

    while (!H.empty())
    {
        K=H.top().next;
        H.pop();
        if (viz[K]==0)
        {
            viz[K]=1;
            for (j=0; j<v[K].size(); j++)
            {
                if (dist[v[K][j].next]>dist[K]+v[K][j].cost&&viz[v[K][j].next]==0)
                {
                    dist[v[K][j].next]=dist[K]+v[K][j].cost;
                    E.next=v[K][j].next;
                    E.cost=dist[v[K][j].next];
                    H.push(E);
                }
            }
        }
    }
}

int main()
{
    freopen ("dijkstra.in","r",stdin);
    freopen ("dijkstra.out","w",stdout);

    int i,n,m;
    int a;

    edge b;

    scanf ("%d %d",&n,&m);

    for (i=1; i<=m; i++)
    {
        scanf ("%d %d %d",&a,&b.next,&b.cost);
        v[a].push_back(b);
    }

    for (i=1; i<=n; i++)
    {
        dist[i]=2000000000;
    }

    Dijkstra(1);

    for (i=2; i<=n; i++)
    {
        if (dist[i]!=2000000000)
        {
            printf ("%d ",dist[i]);
        }
        else
        {
            printf ("0 ");
        }

    }

    printf ("\n");

    return 0;
}