#include <bits/stdc++.h>
#pragma GCC optimize("O1")

using namespace std;

class InputReader
{
public:
    static const int BUFF_SIZE = 1 << 17;
    FILE *fin;
    int bp;
    char buff[BUFF_SIZE];
    InputReader (const char *file_name)
    {
        fin = fopen(file_name, "r");
        bp = BUFF_SIZE - 1;
    }
    void adv()
    {
        if (++bp == BUFF_SIZE)
        {
            fread(buff, sizeof(char), BUFF_SIZE, fin);
            bp = 0;
        }
    }
    InputReader& operator >> (int& num)
    {
        num = 0;
        while (isdigit(buff[bp]) == false)
            adv();
        while (isdigit(buff[bp]))
        {
            num = num * 10 + buff[bp] - '0';
            adv();
        }
        return *this;
    }
};

class ofbuffer
{
private:
    char* b_text;
    int b_capacity, b_size;
    FILE* file;

    inline void b_put_ch( char ch )
    {
        b_text[b_size ++] = ch;
        if ( b_size == b_capacity )
            b_flush();
    }

    void b_put_nr( int x )
    {
        if ( x > 0 )
        {
            b_put_nr( x / 10 );
            b_put_ch( '0' + x % 10 );
        }
    }

public:
    inline ofbuffer( char * path, int capacity = 16000 )
    {
        file = fopen( path, "w" );

        b_text = new char[capacity];
        b_capacity = capacity;
        b_size = 0;
    }

    inline ~ofbuffer()
    {
        if ( b_size != 0 )
            b_flush();
    }

    inline void b_flush( void )
    {
        fwrite( b_text, 1, b_size, file );
        b_size = 0;
    }

    inline ofbuffer &operator<<( int v )
    {
        if ( v == 0 )
            b_put_ch( '0' );
        else
            b_put_nr( v );
        return *this;
    }

    inline ofbuffer &operator<<( char v )
    {
        b_put_ch( v );
        return *this;
    }

    inline void close()
    {
        b_flush();
        fclose( file );
    }
};

InputReader fin("dijkstra.in");
ofbuffer fout("dijkstra.out");

const int MAXN = 50005;
const int oo = 0x3f3f3f3f;

vector < pair < int, int > > v[MAXN];
priority_queue < int, vector < int >, greater < int > > pq;

int dist[MAXN];
int viz[MAXN];

int main()
{
    int n, m, a, b, c, nodcurent, nodvecin, i, lim, cost;

    fin >> n >> m;

    while (m--)
    {
        fin >> a >> b >> c;
        v[a].emplace_back(make_pair(b, c));
    }

    memset(dist, oo, sizeof dist);

    pq.push(1);
    dist[1] = 0;
    viz[1] = 1;

    while (!pq.empty())
    {
        nodcurent = pq.top();
        pq.pop();
        viz[nodcurent] = 0;
        lim = v[nodcurent].size();
        for (i = 0; i < lim; ++i)
        {
            nodvecin = v[nodcurent][i].first;
            cost = v[nodcurent][i].second;
            if (dist[nodcurent] + cost < dist[nodvecin])
            {
                dist[nodvecin] = dist[nodcurent] + cost;
                if (!viz[nodvecin])
                {
                    pq.push(nodvecin);
                    viz[nodvecin] = 1;
                }
            }
        }
    }

    for (i = 2; i <= n; ++i)
    {
        fout << dist[i] % oo << ' ';
    }

    return 0;
}