# include <cstdio>
# include <cstring>
# include <queue>
# include <vector>
using namespace std;

# define verf ++poz == hg ? fread ( ch, 1, hg, stdin ), poz = 0 : 0

const char *FIN = "dijkstra.in", *FOU = "dijkstra.out";
const int MAX = 50005, DIM = 1 << 13, oo = 0x3f3f3f3f;

vector < pair <int, int> > G[MAX];
int N, M, poz, dp[MAX];
char ax[DIM];
bool viz[MAX];
/*
inline void cit(int &x)
{
	x=0;

	while(ax[poz]<'0' || ax[poz]>'9')
	{
		++poz;
		if(poz==DIM) fread(ax, 1, DIM, stdin), poz=0;
	}

	while(ax[poz]>='0' && ax[poz]<='9')
	{
		x=x*10+ax[poz]-'0';
		++poz;
		if(poz==DIM) fread(ax, 1, DIM, stdin), poz=0;
	}
}
*/
struct comp {
    bool operator () (const int &A, const int &B) {
        return dp[A] > dp[B];
    }
};

priority_queue < int, vector <int>, comp > Q ;

void solve (void) {
    memset (dp, oo, sizeof (dp));
    for (dp[1] = 0, Q.push (viz[1] = 1); ! Q.empty (); ) {
        int act = Q.top (); viz[act] = 0; Q.pop ();
        for (vector < pair <int, int> > :: iterator it = G[act].begin (); it != G[act].end (); ++it)
            if (dp[act] + it -> second < dp[it -> first]) {
                dp[it -> first] = dp[act] + it -> second;
                if (viz[it -> first] == 0) {
                    Q.push (it -> first);
                    viz[it -> first] = 1;
                }
            }
    }
}

int main (void) {
    freopen (FIN, "r", stdin);
    freopen (FOU, "w", stdout);
    scanf("%d%d",&N,&M);
    //cit (N), cit (M);
    for (int i = 1, x, y, z; i <= M; ++i) {
        //cit (x), cit (y), cit (z);
        scanf("%d%d%d",&x,&y,&z);
        G[x].push_back (make_pair (y, z));
    }
    solve ();
    for (int i = 2; i <= N; ++i)
        printf ("%d ", dp[i] < oo ? dp[i] : 0);
}